Гра#7885

Гра

1 секунда

64 мегабайти

Легка

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1

Оцінювання

Додатково гарантуються такі умови:

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