POLSKI SPOJ

Jaś i Staś powstanowili zagrać na kartcę w grę Nim. Jest na kartce zapisane N liczb. Chłopcy grają na zmianę. W swojej turze muszą od jednej wybranej przez siebie liczby X odjąć pewną dodatnią liczbę nie większą niż X, następnie przekreślić wybraną liczbę oraz zapisać pod nią wynik odejmowania. Jeśli wynik odejmowania wyniesie 0, to liczba ta nie jest zapisywana. Wygrywa ten, kto jako ostatni wykona ruch, czyli ten kto wyzeruje ostatnią liczbę zapisaną na kartce. Zaczyna zawsze Jaś.

Jaś znając sposób na optymalną strategię prawie zawsze wygrywał. Staś postanowił więc zmienić zasady gry. Postanowił, że liczby na kartce będą zapisane w różnych systemach liczbowych, od systemu dwójkowego po dziesiętny. Jaś jednak nie będzie miał dokładnej informacji, które liczby w jakim systemie zostały zapisane. Oprócz tego Jaś nie może podczas wykonywania ruchu popełnić błędu polegającego na zapisaniu liczby w złym systemie liczbowym po jej zmniejszeniu. Przykładowo jeśli na początku gry zapisane na kartce są dwie liczby: 11 i 9, pierwsza w systemie dwójkowym, a druga w systemie dziesiętnym to Jaś nie może błędnie założyć, że pierwsza liczba jest zapisana w systemie dziesiętnym i zmniejszyć ją do 9. Wykonanie takiego ruchu skutkuje jego natychmiastową przegraną.

Jaś poznając nowe zasady od razu zrozumiał, że znacząco faworyzują one jego przeciwnika, jednak postanowił zgodzić się i zagrać ze Stasiem w ten sposób. Teraz zastanawia się czy jest w ogóle w stanie wygrać w danej grze niezależnie od ruchów Stasia oraz systemów liczbowych w jakich liczby zostały zapisane.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita T (1 ≤ T ≤ 3 * 10³) - liczba zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba N (1 ≤ N ≤ 3 * 10³) przedstawiająca ilość liczb zapisanych na kartce.

W kolejnej linii znajduje się N całkowitych liczb dodatnich przedstawiających liczby zapisane na kartce. Ilość cyfr w każdej z tych liczb jest nie większa niż 6.

Wyjście

Dla każdego zestawu danych należy wpisać "TAK" jeśli Jaś może wygrać niezależnie od ruchów Stasia, oraz systemów w jakich liczby zostały zapisane lub "NIE" jeśli nie może.

Przykład

Wejście:
3
4
1 1 9 11011
3
11 11 11
3
99 99 99

Wyjście:
NIE
NIE
TAK