Efficient Algotithms 2022

Jadąc tramwajem nierzadko czytamy jakieś materiały. Niestety często zdarza się, że są one na pojedynczych kartkach. Sprawia to masę problemów. Pominąwszy fakt, że kartki mogą być nie po kolei, to w dodatku niektóre mogą być obrócone o 180˚ w stosunku do prawidłowej pozycji. Zakładamy, że wszystkie kartki są zadrukowane jednostronnie oraz że wszystkie są ułożone tak, że strona zadrukowana jest z góry. Zestaw taki można czytać w następujący sposób. Po pierwsze, jeśli początkowa strona jest źle obrócona, to obracamy cały zestaw kartek o 180˚. Później w każdym kroku wykonujemy następujące czynności:

• czytamy kartkę, która jest na wierzchu,
• podnosimy ją nad resztę
• pozostały zestaw (złożony z wszystkich kartek oprócz tej, którą podnieśliśmy) obracamy tak, by wierzchnia kartka tego zestawu była prawidłowo obrócona
• bez żadnych obrotów wkładamy kartkę, którą podnieśliśmy, na spód.

Czynności te można wykonywać w nieskończoność (zaniedbujemy fakt powtórnego czytania tych samych kartek). Powstaje naturalne pytanie, czy w którymś momencie wszystkie kartki będą poprawnie obrócone i jeśli tak, to po której rundzie. Runda polegająca na ewentualnym obróceniu całego zestawu ma numer 1, następne zaś 2, 3, ...

Zadanie

Twoim zadaniem jest napisanie programu, który dla danej liczby kartek n oraz początkowego ich ułożeń a_i {0; 1} (a_i = 0 oznacza kartkę nieobróconą, a_i = 1 { obróconą o 180˚) stwierdzi czy kiedykolwiek wszystkie kartki będą poprawnie obrócone, a jeśli tak to po której rundzie nastąpi to po raz pierwszy (jeśli wszystkie na początku są dobrze ułożone, tj. a₁ = a₂ = ... = a_n = 0, odpowiedzią jest 0).

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba naturalna d (1 ≤ d ≤ 10), określająca liczbę zestawów danych, których opisy umieszczone są kolejno po sobie w następnych liniach pliku. Opis pojedynczego zestawu jest następujący:

W pierwszej linii znajduje się jedna liczba naturalna n (1 ≤ n ≤ 10000) określająca liczbę kartek. W kolejnej znajduje się ciąg n liczb a₁, a₂ ... a_n (a_i należy do przedziału {0; 1}) określających początkowe obrócenie kolejnych kartek zgodnie z regułą podaną w treści zadania.

Specyfikacja wyjścia

Każdemu zestawowi na wejściu powinna odpowiadać jedna linia wyjścia. Ta linia powinna zawierać albo liczbę naturalną r określającą najmniejszy numer rundy, po której wszystkie kartki będą poprawnie obrócone (tzn. nieobrócone) lub słowo NIGDY jeśli taka sytuacja nigdy nie nastąpi.

Przykład

Wejście:
3
3
0 0 0
3
0 1 0
3
1 0 0

Wyjście:
0
NIGDY
2

---

While riding public communication it is not uncommon to read some content. Unfortunately, it often happens that they are on single pages. This causes a lot of problems. Apart from the fact that the pages may not be in the right order, some of them may be rotated by 180˚ in relation to the correct position. 

We assume that all pages are printed on one side and that they are all arranged in such a way that the printed side is facing up. Such a set can be read as follows. First, if the initial page is wrongly rotated, we rotate the entire set of cards 180˚. Later, in each step, we do the following:

• we read the page that is on top,
• lift it above the rest
• turn the remaining set (consisting of all the pages except the one you picked up) so that the top card of this set is turned correctly
• without any rotation put the card you picked up on the bottom.

These actions can be performed infinitely (we neglect the fact of rereading the same cards). The natural question that arises is whether at some point all the cards will be correctly turned, and if so, after which round. The round involving the eventual turning of the entire set is numbered 1, while the next rounds are 2, 3, ...

Your task is to write a program that, for a given number of pages n and their initial arrangement {0/1} (0 means a page not rotated, 1 means rotated 180˚) will determine if all the pages will ever be rotated correctly, and if so, after which round it will happen for the first time (if all of them are well arranged at the beginning, i.e., a1 = a2 = ... = an = 0, the answer is 0).

Input

The first line of the input contains a natural number d (1 ≤ d ≤ 10), specifying the number of data sets whose descriptions are placed sequentially in the following lines of the input. The description of a single set is as follows:

The first line contains one natural number n (1 ≤ n ≤ 10000) specifying the number of cards. In the next line there is a sequence of n numbers a1, a2 ... an (ai belongs to {0; 1} set) specifying the initial rotation of successive pages according to the rule given in the body of the task.

Output

Each set in the input should correspond to one line of output. This line should contain either a natural number r specifying the smallest number of rounds after which all cards will be correctly rotated (i.e., not rotated) or the word NIGDY if this situation never occurs.

Example

Input:
3
3
0 0 0
3
0 1 0
3
1 0 0

Output:
0
NIGDY
2