Двоє грають у таку гру. На столі у ряд розкладено N купок сірників. Перший гравець на першому кроці має взяти один сірник із першої купки. Другий гравець на наступному кроці може взяти один сірник із першої або другої купки, або ж із кожної з них. Перший гравець на третьому кроці може при бажанні взяти по одному сірнику з будь-яких із перших трьох купок, але має взяти хоча б із одної з них. Потім другий гравець може брати сірники з перших чотирьох купок, і так далі. Після N - го кроку гри кожен із гравців може брати по одному сірнику з будь-яких купок, але хоча б із одної. Виграє той, хто забере останній сірник.

Завдання

Напишіть програму, яка за інформацією про початкові розміри купок визначить, який гравець має виграти при оптимальній стратегії.

Вхідні дані

Перший рядок вхідних даних містить єдине ціле число T (1 ≤ T ≤ 10). T наступних рядків містять описи тестів (по 1 на рядок) у такому форматі: спочатку ціле число N (1 ≤ N ≤ 1000), потім N цілих чисел – розміри купок. Кожне з них не перевищує 1000. Гарантується, що сума N щодо всіх тестів не перевищує 10000.

Вихідні дані

Вихідні дані повині містити стільки T рядків. Кожен наступних рядок має містити одне число: 1 – якщо при оптимальній грі у відповідному тесті перемагає перший гравець, 2 – якщо другий.

Оцінювання

Додатково гарантуються такі умови: 1. Для 20% тестів T=3 та всі N=3, у кожній купці до 5 сірників. 2. Для 20% тестів T=3 та всі N=3, у кожній купці не більше 5 сірників. 3. Для 20% тестів T=6 та всі N=3, у кожній купці не більше 6 сірників. 4. Для решти 40% тестів додаткових обмежень немає.