\includegraphics{https://static.e-olymp.com/content/a6/a6582d9fa4b6362f14beccc4fc8283d837f43a8c.jpg} \textit{Рисунок Шишко Марины - 12.05.2010, 9 кл.} Наконец-то Печкин начал приносить для Шарика обещанные косточки... Так как косточек было много, а приближалась зима, Шарик начал складировать их по кучкам, причем в каждой кучке не более \textbf{100} косточек, а всего кучек не более, чем \textbf{10000}. "\textit{Замяучили меня эти споры по поводу двоичной или троичной логики}" - подумал Матроскин, - "\textit{ведь все-равно троичную можно свести к двоичной}", решил умный кот и тут же придумал новую игру. Он пронумеровал все кучки подряд и предложить Шарику не просто сидеть и ждать очередного прихода Печкина, а поиграть с ним в такую игру. Ходят по очереди, но Матроскин всегда первым. Игрок, делающий ход, сначала выбирает кучку с количеством косточек \textbf{A}, а потом \textbf{B}, соблюдая следующие требования: \begin{itemize} \item Кучка \textbf{A} должна быть не пустой. \item Кучка \textbf{B} должна быть строго меньше за \textbf{A}. \item Кучка \textbf{B} также должна быть не пустой. \item Обязательно должны выполнятся условия, что суммарно количество \textbf{A + B }не делится нацело на \textbf{2} и делится нацело на \textbf{3} (к вопросу о двоичной и троичной логиках... :) ). \item Из кучки \textbf{B} взять произвольное, но больше нуля количество косточек. \item Кто не смог сделать ход - тот проиграл. \end{itemize} Кто выигрывает в этой игре при оптимальной стратегии обеих игроков? \InputFile В первой строке задано количество игр между Матроскиным и Шариком за день \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Далее идет \textbf{T }строк, в каждой из которых сначала задано количество кучек \textbf{N}, а потом \textbf{N} чисел, определяющих количество косточек в соответсвующей кучке. \OutputFile Вывести одну строку, состоящую из последовательности \textbf{T} единиц или двоек: \textbf{1} - если выиграл Матроскин, \textbf{2} - Шарик.