G. Полоска, фишка, два игрока
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана полоска из $$$n + 1$$$ клетки, которые пронумерованы числами от $$$1$$$ до $$$n + 1$$$. Изначально, на клетке под номером $$$1$$$ стоит фишка с силой $$$1$$$ и на клетках с номерами $$$1, 2, \ldots, n$$$ записаны числа $$$a_1, a_2, \ldots, a_n$$$ соответственно.

Два игрока играют в игру. Каждым ходом игрок совершает следующие действия последовательно:

  1. Пусть фишка находится на клетке под номером $$$i$$$.
  2. Игрок может увеличить силу фишки на любое целое число от $$$0$$$ до $$$a_i$$$ включительно.
  3. Затем игрок перемещает фишку на любое целое положительное число, не превосходящее силы фишки, клеток вперед, так, что фишка не выходит за границы полоски после этого действия.

Выигрывает игрок, после чьего хода фишка окажется на клетке $$$n + 1$$$.

Кто выигрывает при оптимальной игре?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество записанных чисел.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — числа записанные на клетках.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, $$$1$$$ или $$$2$$$ — номер игрока, выигрывающего при оптимальной игре. (Игрок $$$1$$$ делает первый ход.)

Пример
Входные данные
4
3
0 0 0
3
1 1 2
5
0 0 1 0 0
9
0 1 2 0 0 1 0 0 0
Выходные данные
1
2
1
2
Примечание

В первом наборе входных данных, сила фишки на протяжении всей игры равна $$$1$$$, поэтому каждый ход игроки обязаны ходить ровно на одну клетку вперёд. Так пройдёт $$$3$$$ хода, и последний ход сделает игрок $$$1$$$, поэтому он в любом случае выиграет.

Во втором наборе входных данных, у игрока $$$2$$$ есть выигрышная стратегия: в первый же свой ход увеличить силу фишки как можно больше, а затем прыгнуть на клетку $$$4$$$ и выиграть. Это всегда возможно, так как фишка в начале хода будет находиться на клетке $$$2$$$ или $$$3$$$, и её силу можно увеличить хотя бы до $$$2$$$.