Słowa

Limit pamięci: 64 MB

Niech będzie funkcją określoną na napisach złożonych z cyfr 0 i 1. Funkcja przekształca napis , zastępując (niezależnie i równocześnie) każdą cyfrę 0 przez 1 i każdą cyfrę 1 przez napis . Na przykład , (tzn. funkcja zastosowana do pustego napisu jest pustym napisem). Zauważmy, że jest różnowartościowa. Przez oznaczmy -krotne złożenie funkcji ze sobą. W szczególności, to funkcja identycznościowa .

Interesują nas napisy postaci dla Oto kilka pierwszych takich napisów:

, , , , , .

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą , , oznaczającą liczbę przypadków testowych do rozważenia. Pierwszy wiersz opisu każdego przypadku zawiera jedną liczbę całkowitą , . W drugim wierszu opisu znajduje się nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Suma liczb z drugiego wiersza każdego przypadku jest nie większa niż .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy, po jednym dla każdego przypadku testowego. Wiersz odpowiadający danemu przypadkowi testowemu powinien zawierać jedno słowo: TAK - jeśli w tym przypadku jest podsłowem dla pewnego , lub NIE w przeciwnym razie.

Przykład

Dla danych wejściowych:

2
2
1 2
2
2 0

poprawną odpowiedzią jest:

TAK
NIE

Wyjaśnienie do przykładu: Słowo z pierwszego przypadku testowego to - jest ono podsłowem na przykład słowa . W drugim przypadku testowym występuje słowo , które nie jest podsłowem żadnego słowa postaci .

Autorzy zadania: Wojciech Rytter, Bartosz Walczak.