G. Stripe, Token and Two Players
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a stripe of $$$n + 1$$$ cells, numbered from $$$1$$$ to $$$n + 1$$$. Initially, there is a token with power $$$1$$$ on cell number $$$1$$$, and the numbers $$$a_1, a_2, \ldots, a_n$$$ are written on cells $$$1, 2, \ldots, n$$$ respectively.

Two players play a game. On each move, the player performs the following actions in order:

  1. Suppose the token is on cell number $$$i$$$.
  2. The player may increase the power of the token by any integer from $$$0$$$ to $$$a_i$$$ inclusive.
  3. Then the player moves the token forward by any positive integer not exceeding the token's power, such that after this action the token does not leave the stripe.

The player after whose move the token lands on cell $$$n + 1$$$ wins.

Who wins with optimal play?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of written numbers.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers written on the cells.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output one integer, $$$1$$$ or $$$2$$$ — the number of the player who wins with optimal play. (Player $$$1$$$ makes the first move.)

Example
Input
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
Output
1
2
1
2
Note

In the first test case, the power of the token remains equal to $$$1$$$ throughout the game, so on every move the players must move exactly one cell forward. Thus, $$$3$$$ moves will be made, and the last move will be made by player $$$1$$$, so he will win in any case.

In the second test case, player $$$2$$$ has a winning strategy: on their very first move, increase the token's power as much as possible, and then jump to cell $$$4$$$ and win. This is always possible, since at the start of the move the token will be on cell $$$2$$$ or $$$3$$$, and its power can be increased to at least $$$2$$$.