Game#7885
Two players are engaged in a game involving 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 -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.
Develop a program that, given the initial sizes of the piles, determines which player will win if both play optimally.
The input begins with a single integer (1 \leq T \leq 10), representing the number of test cases. Each of the following lines describes a test case with the format: an integer (1 \leq N \leq 1000) followed by integers indicating the sizes of the piles. Each pile size does not exceed . The total sum of across all test cases does not exceed .
The output should consist of lines. Each line should contain the number if the first player wins with optimal play in the corresponding test case, or if the second player wins.
Example 1
The following conditions are guaranteed:
For of the test cases, T = 3 and all N = 3, with each pile containing up to matches.
For another of the test cases, T = 3 and all N = 3, with each pile containing no more than matches.
For an additional of the test cases, T = 6 and all N = 3, with each pile containing no more than matches.
The remaining of the test cases have no additional restrictions.