Problem description

Rozważmy modyfikację gry Nim – kwadratowy Nim. W tej dwuosobowej grze tej jest kilka stosów kamieni. Ruch w grze polega na wybraniu jednego stosu i zabraniu z niego pewnej liczby kamieni. Zabierana liczba kamieni musi być kwadratem liczby naturalnej. Gracz, który nie może wykonać ruchu zgodnego z zasadami gry przegrywa (dzieje się tak wtedy, gdy nie ma już żadnych kamieni).

Powiemy, że gracz ma strategię wygrywającą, jeśli jest w stanie (grając optymalnie) wygrać, niezależnie od posunięć przeciwnika.

Napisz program, który: wczyta wiele opisów gier w kwadratowego Nima, wyznaczy dla każdej z nich czy gracz rozpoczynający ma strategię wygrywającą i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zestawów danych. W kolejnych 2Q wierszach znajduje się opis kolejnych zestawów danych. Opis każdego zestawu danych składa się z dwóch wierszy. Pierwszy wiersz opisu zawiera jedną liczbę naturalną N – liczbę stosów w danej grze. Drugi wiersz opisu zawiera ciąg N liczb naturalnych A_i – liczby kamieni na kolejnych stosach w grze.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź do i-tego zestawu danych – TAK jeśli gracz rozpoczynający ma strategię wygrywającą lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ Q ≤ 100 000, 1 ≤ N ≤ 100 000, 1 ≤ A_i ≤ 250 000.

Suma wartości N (liczby stosów) we wszystkich zestawach danych nie przekracza miliona.

Przykład

4
3
1 1 1
3
1 1 2
4
2 3 4 10
4
2 3 4 25

TAK
NIE
TAK
NIE