\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} - Шарик.