csir

Un şir circular este un şir format numai din caracterele A şi B care are următoarele proprietăţi:

• are lungime N >= 1 (nu poate fi şirul vid);
• se consideră că după ultimul caracter din şir urmează primul caracter din şir.

Această proprietate implică faptul că orice şir circular are N subsecvenţe de lungime L (1 <= L <= N).

O subsecvenţă de lungime L a unui şir circular S este un şir de caractere (obişnuit, nu circular) format din L caractere aflate pe poziţii consecutive în şirul S. De exemplu, şirul circular ABAAB are 5 subsecvenţe de lungime 3 : ABA, BAA, AAB, ABA şi BAB (ele nu sunt distincte ca valoare, însă diferă ca poziţie de început în şirul din care fac parte).

Un cşir este un şir circular care are în plus următoarea proprietate: pentru orice L (1 <= L <= N) şi oricare două subsecvenţe de lungime L (să le numim S1 şi S2), numărul de caractere A din S1 diferă faţă de numărul de caractere A din S2 cu cel mult 1 (în valoare absolută).

Să considerăm şirul circular BBAABAA. Acest şir nu este un cşir, deoarece există subsecvenţele BBAAB şi AABAA (de lungime 5), care conţin 2, respectiv 4 caractere A (diferenţa dintre numărul de caractere A este, astfel, 2). De asemenea, şirul ABABAABAAB nu este un cşir, deoarece conţine subsecvenţe AABAA şi BABAB pentru care diferenţa dintre numărul de caractere A este mai mare decât 1 (în valoare absolută).

Şirurile circulare ABA şi AABABAAB sunt, în schimb, cşir-uri, deoarece oricare ar fi două subsecvenţe S1 şi S2 având aceeaşi lungime, diferenţa dintre numărul de caractere A din S1 şi numărul de caractere A din S2 este mai mică sau egală cu 1 (în valoare absolută).

Cerinţă

Dându-se mai multe şiruri circulare, determinaţi dacă ele sunt cşir-uri.

Date de intrare

Prima linie a fişierului de intrare csir.in conţine numărul întreg S, reprezentând numărul de şiruri conţinute în fişier. Pe fiecare dintre următoarele S linii se află câte un şir circular.

Date de ieşire

În fişierul de ieşire csir.out se vor scrie S linii. Pe a K-a linie din acest fişier, se va afişa 1, dacă al K-lea şir din fişierul de intrare este un cşir, sau 0, în caz contrar.

Restricţii şi precizări

• 1 <= S <= 20
• Lungimea fiecărui şir circular din fişierul de intrare este cuprinsă între 1 şi 50000 (inclusiv).
• Şirurile conţin numai caracterele A şi B (nu şi a sau b).
• Nu se acordă punctaje parţiale.

Exemplu

csir.in

4
BBAABAA
ABABAABAAB	
ABA
AABABAAB

csir.out

0
0
1
1