Fișierul intrare/ieșire	an.in, an.out	Sursă	ONI 2017, Baraj Gimnaziu
Autor	autor necunoscut	Adăugată de	Tudor Mocioi • tgm000
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

An (baraj gimnaziu)

Ana și Bogdan au inventat încă un joc. Jocul are jetoane, albe și negre, care inițial se așază într-un teanc, într-o ordine oarecare. Numim configurație succesiunea culorilor tuturor jetoanelor din teanc (în ordine, începând din vârful teancului). Un jeton alb va fi codificat prin litera A, iar un jeton negru prin litera N.
La o mutare un jucător poate lua din vârful teancului oricâte jetoane consecutive (dar cel puțin un jeton), cu condiția ca toate jetoanele luate să aibă aceeași culoare. Jucătorii mută alternativ, prima la mutare fiind Ana. Jocul va fi câștigat de jucătorul care ia ultimul jeton.
Spunem că un jucător are strategie sigură de câștig dacă el, urmând această strategie, câștigă jocul, indiferent care sunt mutările celuilalt jucător.

Cerință

Scrieți un program care citește T configurații și determină pentru fiecare dintre cele T configurații dacă Ana are strategie sigură de câștig.

Date de intrare

Fișierul de intrare an.in conține pe prima linie un număr natural T care reprezintă numărul de configurații. Pe următoarele T linii sunt scrise cele T configurații, câte o configurație pe o linie, sub forma unei succesiuni de litere din mulțimea {A, N}.

Date de ieșire

Fișierul de ieșire an.out va conține T linii. Pe a i-a linie va fi scrisă valoarea 1 dacă Ana are strategie sigură de câștig pentru cea de a i-a configurație din fișierul de intrare, respectiv valoarea 0 în caz contrar.

Restricții

• 1 < T ≤ 50
• 0 < numărul de jetoane din orice configurație ≤ 10.000

Exemplu