Є \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} - номерів гравців, які переможуть.