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
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.