E - Transofmracje

Autor: Piotr Zieliński

Mamy dany zero-jednkowy wektor T o długości N. Możemy go przetransformować w nowy wektor T' zgodnie z następującym wzorem:

     T'[i] = T[i] xor T[i+1]   i = 1,2,...,N-1
     T'[N] = T[N] xor T[1]

Tak powstały wektor można znowu przetranformować, i znowu, i znowu, ..., i tak w nieskończoność. Czy w ten sposób kiedyś dojdziemy do wektora zawierajacego wyłącznie zera?

Wejście

Pierwszy wiersz wejścia zawiera liczbę rozważanych wektorów. Dla każdego z wektorów na wejściu pojawia się jego długość N (2 ≤ N ≤ 100000) oraz N-elementow ciąg zer i jedynek.

Wyjście

Dla każdego wektora należy wypisać "TAK" jeżeli po którejś transformacji otrzymamy wektor złożony z samych zer lub "NIE" w przeciwnym przypadku.

Przykładowe wejście

3
3
0 0 0
5
1 1 0 1 1
4
1 0 1 0

Przykładowe wyjście

TAK
NIE
TAK