Kristína veľmi rada skúma mŕtve jazyky a už oddávna je vysoko postavenou členkou Klubu Starobylých Prekladateľov. Celý klub srší aktivitou, lebo archeológovia objavili na dne Atlantického oceánu ruiny Atlantídy a v nich perfektne zachované vodotesné zvitky. Všetkým členom klubu je jasné, že prvý, komu sa podarí preložiť atlančinu do moderných jazykov, získa obrovskú slávu a naveky sa zapíše do dejín nekrolingvistiky.

Od pochopenia významu textu je ešte ďaleko, ale Kristína si už všimla jedno kľúčové pozorovanie: vyzerá, že atlanťania píšu každé slovo dvakrát, raz odpredu a raz odzadu. Kto vie, či je to poistenie proti prípadnému poškodeniu zvitku, alebo to má v atlantickej kultúre nejaký iný dôvod…

Kristína by si chcela overiť, či je jej hypotéza naozaj správna. Lenže v atlančine sa medzi slovami nepíšu medzery, takže to nie je také ľahké skontrolovať.

Úloha

Váš program dostane niekoľko reťazcov textu v atlančine. O každom reťazci musíte zistiť, či sa dá rozdeliť na slová tak, aby spĺňali Kristíninu hypotézu. Čiže po každom (nepárnom) slove musí nasledovať to isté slovo naopak.

Formát vstupu

V prvom riadku vstupu je číslo $t$ udávajúce počet reťazcov.

Na každom z ďalších $t$ riadkoch je neprázdny reťazec zložený z malých a veľkých písmen anglickej abecedy. Malé a veľké písmená považujeme za rôzne.

Dĺžku najdlhšieho reťazca na vstupe si označme $n$. (Toto číslo je len na vysvetlenie a na vstupe sa nepíše.) V jednotlivých sadách platia nasledujúce obmedzenia:

Navyše v sade 3 sú vstupy nejakým bližšie nešpecifikovaným spôsobom ľahšie.

Formát výstupu

Vypíšte $t$ riadkov a na každom jedno číslo: $1$, ak sa ten reťazec nejako dá rozdeliť na slová požadovaným spôsobom, alebo $0$, ak nedá.

Príklad

Input:

6
rummur
deedee
aaaaaaa
kajak
abcxxyycba
mMmMmM

Output:

1
1
0
0
0
0

“rummur” sa dá rozdeliť na “rum mur”, a “deedee” na “de ed e e”.