Розділити чи забрати?

Є N купок з камінчиками. За один хід дозволяється або забрати довільну кількість камінчиків з однієї купки, або розділити купку на дві менші. Перемагає той, хто забирає останній камінчик.

Потрібно визначити, хто перемагає при оптимальній стратегії обох гравців: той, хто робить хід першим, чи другим.

Вхідні дані

У першому рядку задано кількість тестових випадків T (1 <= T <= 100) Далі йде T пар рядків, у першому з яких знаходиться значення N, а у другому через пропуск кількості камінчиків у кожні з купок S_i.

1 <= N <= 10^3

1 <= S_i <= 10^6

Вихідні дані

Єдиний рядок, який містить послідовність T 1 і 2 - номерів гравців, які переможуть.

Приклади