Задачі
Розділити чи забрати?
Розділити чи забрати?
Є \textbf{N} купок з камінчиками. За один хід дозволяється або забрати довільну кількість камінчиків з однієї купки, або розділити купку на дві менші. Перемагає той, хто забирає останній камінчик.
Потрібно визначити, хто перемагає при оптимальній стратегії обох гравців: той, хто робить хід першим, чи другим.
\InputFile
У першому рядку задано кількість тестових випадків \textbf{T} (\textbf{1} <= \textbf{T} <= \textbf{100}) Далі йде \textbf{T} пар рядків, у першому з яких знаходиться значення \textbf{N}, а у другому через пропуск кількості камінчиків у кожні з купок \textbf{S_i}.
\textbf{1} <= \textbf{N} <= \textbf{10^3}
\textbf{1} <= \textbf{S_i} <= \textbf{10^6}
\OutputFile
Єдиний рядок, який містить послідовність \textbf{T} \textbf{1} і \textbf{2} - номерів гравців, які переможуть.
Вхідні дані #1
2 3 2 2 3 2 3 3
Вихідні дані #1
12