Game
Two players are engaged in a game involving N piles of matches lined up in a row on a table. The game proceeds as follows:
On the first move, the first player must take one match from the first pile.
On the second move, the second player can choose to take one match from either the first or second pile, or one match from each of them.
On the third move, the first player may take one match from any of the first three piles, but must take at least one match.
The second player on the fourth move can take matches from any of the first four piles, and so on.
After the N-th move, each player can take one match from any pile, but must take at least one match.
The winner is the player who takes the last match.
Task
Develop a program that, given the initial sizes of the piles, determines which player will win if both play optimally.
Input
The input begins with a single integer T (1 ≤ T ≤ 10), representing the number of test cases. Each of the following T lines describes a test case with the format: an integer N (1 ≤ N ≤ 1000) followed by N integers indicating the sizes of the piles. Each pile size does not exceed 1000. The total sum of N across all test cases does not exceed 10000.
Output
The output should consist of T lines. Each line should contain the number 1 if the first player wins with optimal play in the corresponding test case, or 2 if the second player wins.
Evaluation
The following conditions are guaranteed:
For 20% of the test cases, T=3 and all N=3, with each pile containing up to 5 matches.
For another 20% of the test cases, T=3 and all N=3, with each pile containing no more than 5 matches.
For an additional 20% of the test cases, T=6 and all N=3, with each pile containing no more than 6 matches.
The remaining 40% of the test cases have no additional restrictions.