Bones for Sharik 2
Figure Szyszko Marina - 12.05.2010, 9 cl.
Finally Pechkin begun to yield to Schariks promised bones ... Since the bones were many, and winter approached, Scharik began to stow on a handful, with each pile of 100 stones, and heaps of not more than 10000.
"Zamyauchili me these disputes over the binary or ternary logic" - thought Matroskin, - "after all, still the ternary can be reduced to a binary", decided clever cat, and immediately thought of a new game. He has numbered all the piles in a row and Scharik does not offer to just sit and wait for the next coming Pechkin, and play with him in this game. Take turns, but Matroskin always first. The player makes a move first selects a handful of the number of pits A, then B, subject to the following requirements:
A handful of A must be empty.
A handful of B must be strictly less than for A.
A handful of B must also be empty.
Must be executed provided that the total number of A+B is not divisible evenly by 2 and divided evenly by 3 (to the question of binary and ternary logics ...:) ).
Of the handful of B is arbitrary, but greater than zero the number of seeds.
Who could not make a move - he lost.
Who wins in this game with an optimal strategy for both players?
A handful should not be empty.
Input
The first line is given the number of games between Matroskin and Scharik of the day T (1 ≤ T ≤ 100). Next comes the T lines, each of which first set the number of piles of N, then N numbers, determining the number of seeds in the appropriate pile.
Output
Print a single line consisting of a sequence of T units or dyads: 1 - if won Matroskin, 2 - Scharik.
Print a single line consisting of a sequence of T units or dyads: 1 - if won Matroskin, 2 - Ball.