Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FIBGAME - Gra Fibonacciego

Ciąg słów Fibonacciego fi definujemy w następujący sposób: f1=a, f2=b oraz fi=fi-2fi-1. Inaczej mówiąc, słowo Fibonacciego o numerze i powstaje przez połączenie ze sobą słów o numerach i-2 i i-1. Na przykład: f3=ab, f4=bab, f5=abbab.

W grę Fibonacciego gra dwóch graczy. Grają oni na słowie składającym się z liter a i b (słowo to będziemy nazywali planszą). Gracze wykonują na przemian ruchy polegające na skreślaniu dowolnego słowa Fibonacziego z prawego końca planszy. Przegrywa ten gracz, który nie może wykonać kolejnego ruchu. Twoim zadaniem jest stwierdzenie, czy dla danego słowa gracz wykonujący pierwszy ruch zawsze może wygrać.

Zadanie

Napisz program który wczyta liczbę zestawów testowych i dla każdego zestawu:

  • wczyta ze standardowego wejścia słowo, na którym toczy się gra,
  • określi, czy pierwszy gracz zawsze może wygrać,
  • wypisze odpowiedź na standardowe wyjście.

 

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita t (0<t<11). Jest to liczba przypadków testowych, które pojawią sie na standardowym wejściu. Przypadki testowe opisane są w kolejnych t  wierszach, jeden przypadek w jednym wierszu. Każdy z tych t wierszy zawiera dodatnią liczbę całkowitą n (0<n<=106), a następnie po spacji ciąg liter a  i b długości n, nieoddzielonych spacjami. Jest to słowo, na którym toczy się gra.

Wyjście

Na standardowe wyjście powinno zostać wypisane t wierszy. Każdy wiersz powinien zawierać odpowiedź do jednego przypadku testowego, w takiej samej kolejności w jakiej pojawiły się one na wejściu. Odpowiedzią powinno być słowo TAK, gdy pierwszy gracz może zawsze wygrać, lub NIE w przeciwnym wypadku.

Przykład

Wejście:
2
5 aaaaa
10 abbababbaa

Wyjście:
TAK
NIE


Dodane przez:Piotr Kąkol
Data dodania:2011-09-22
Limit czasu wykonania programu:0.100s-0.330s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Pogromcy Algorytmów 2002
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.