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?
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.
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.
3 3 0 0 0 5 1 1 0 1 1 4 1 0 1 0
TAK NIE TAK