Игра
Два игрока участвуют в следующей игре. На столе в ряд расположены N кучек спичек. Первый игрок в своем первом ходе обязан взять одну спичку из первой кучки. Второй игрок на своем ходе может взять одну спичку из первой или второй кучки, либо по одной спичке из каждой из них. На третьем ходе первый игрок может взять по одной спичке из любых из первых трех кучек, но должен взять хотя бы одну. Затем второй игрок может брать спички из первых четырех кучек, и так далее. После N-го хода каждый из игроков может брать по одной спичке из любых кучек, но хотя бы из одной. Побеждает тот, кто заберет последнюю спичку.
Задание
Напишите программу, которая по информации о начальных размерах кучек определит, какой игрок выиграет при оптимальной стратегии.
Входные данные
Первая строка входных данных содержит одно целое число T (1 ≤ T ≤ 10). В следующих T строках содержатся описания тестов (по одному на строку) в следующем формате: сначала целое число N (1 ≤ N ≤ 1000), затем N целых чисел, представляющих размеры кучек. Каждое из этих чисел не превышает 1000. Гарантируется, что сумма всех N по всем тестам не превышает 10000.
Выходные данные
Выходные данные должны содержать T строк. Каждая строка должна содержать одно число: 1, если при оптимальной игре в соответствующем тесте побеждает первый игрок, или 2, если второй.
Примеры
Оценивание
Дополнительно гарантируются следующие условия:
Для 20% тестов T=3 и все N=3, в каждой кучке до 5 спичек.
Для 20% тестов T=3 и все N=3, в каждой кучке не более 5 спичек.
Для 20% тестов T=6 и все N=3, в каждой кучке не более 6 спичек.
Для оставшихся 40% тестов дополнительных ограничений нет.