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:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq t \leq\) | \(20\) | \(20\) | \(20\) | \(20\) |
\(1 \leq n \leq\) | \(30\) | \(10^3\) | \(10^5\) | \(10^6\) |
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”.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.