Kamyki

Limit pamięci: 128 MB

Jaś i Małgosia grają w "kamyki". Początkowo na stole ułożona jest pewna liczba kamyków, pogrupowanych w kupek. Kupki znajdują się obok siebie w jednym rzędzie. Ustawienie kamieni spełnia dodatkowo własność, że na każdej kupce jest nie mniej kamieni niż na kupce sąsiadującej z nią po lewej (nie dotyczy to pierwszej kupki, na lewo od której nie ma już nic). Gracze na przemian usuwają z jednej, wybranej przez siebie w danym ruchu kupki dowolną dodatnią liczbę kamieni. Muszą to jednak robić tak, aby na tej kupce nie zostało mniej kamieni niż na kupce o jeden w lewo. Początkowa własność ustawienia zostaje więc zachowana. Gdy ktoś nie ma już możliwości wykonania ruchu (tzn. przed jego ruchem wszystkie kamienie są zdjęte ze stołu), to przegrywa. Jaś zawsze zaczyna.

Małgosia jest bardzo dobra w tę grę i jeśli tylko może, to gra tak, aby wygrać. Jaś prosi Cię o pomoc - chciałby wiedzieć, czy przy danym ustawieniu początkowym ma w ogóle szanse wygrać z Małgosią. Napisz program, który to określi.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę ustawień początkowych gry do przeanalizowania. W kolejnych wierszach znajdują się opisy tych ustawień; każdy z nich zajmuje dokładnie dwa wiersze.

W pierwszym wierszu każdego opisu znajduje się jedna liczba całkowita , - liczba kupek kamieni. W drugim wierszu opisu znajduje się nieujemnych liczb całkowitych , pooddzielanych pojedynczymi odstępami i reprezentujących liczby kamieni na poszczególnych kupkach, od lewej do prawej. Liczby te spełniają nierówności . Łączna liczba kamieni w żadnym opisie nie przekracza .

Wyjście

Na standardowe wyjście powinno zostać wypisanych wierszy. W -tym wierszu wyjścia (dla ) powinno znajdować się słowo TAK, jeśli Jaś może wygrać, zaczynając z -tego na wejściu ustawienia początkowego, lub słowo NIE, jeśli Jaś zawsze przegra przy optymalnej grze Małgosi.

Przykład

Dla danych wejściowych:

2
2
2 2
3
1 2 4

poprawną odpowiedzią jest:

NIE
TAK

Autor zadania: Paweł Parys.