Гра

Двоє грають у таку гру. На столі у ряд розкладено 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% тестів додаткових обмежень немає.

Приклади