\includegraphics{https://static.e-olymp.com/content/a6/a6582d9fa4b6362f14beccc4fc8283d837f43a8c.jpg} \textit{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 \textbf{100} stones, and heaps of not more than \textbf{10000}. "\textit{Zamyauchili me these disputes over the binary or ternary logic}" - thought Matroskin, - "\textit{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 \textbf{A}, then \textbf{B}, subject to the following requirements: \begin{itemize} \item A handful of \textbf{A} must be empty. \item A handful of \textbf{B} must be strictly less than for \textbf{A}. \item A handful of \textbf{B} must also be empty. \item Must be executed provided that the total number of \textbf{A}+\textbf{B} is not divisible evenly by \textbf{2 }and divided evenly by \textbf{3} (to the question of binary and ternary logics ...:) ). \item Of the handful of \textbf{B} is arbitrary, but greater than zero the number of seeds. \item Who could not make a move - he lost. \end{itemize} Who wins in this game with an optimal strategy for both players? A handful should not be empty. \InputFile The first line is given the number of games between Matroskin and Scharik of the day \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Next comes the \textbf{T} lines, each of which first set the number of piles of \textbf{N}, then \textbf{N} numbers, determining the number of seeds in the appropriate pile. \OutputFile Print a single line consisting of a sequence of \textbf{T} units or dyads: \textbf{1} - if won Matroskin, \textbf{2} - Scharik. Print a single line consisting of a sequence of T units or dyads: 1 - if won Matroskin, 2 - Ball.