题目描述

有一条由 $n+1$ 个格子组成的条带，编号从 $1$ 到 $n+1$。初始时，一个力量为 $1$ 的棋子位于第 $1$ 格，第 $1,2,\ldots,n$ 格上分别写着数字 $a_1,a_2,\ldots,a_n$。

两名玩家进行游戏。每一步，当前玩家依次执行以下操作：

• 假设棋子位于第 $i$ 格。
• 玩家可以将棋子的力量增加 $0$ 到 $a_i$（含）之间的任意整数。
• 然后玩家将棋子向前移动不超过棋子力量的任意正整数格，且移动后棋子不能超出条带范围。

在某位玩家移动后棋子到达第 $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$ 执行，因此玩家 $1$ 必胜。

在第二个测试用例中，玩家 $2$ 有必胜策略：在第一步中尽可能增加棋子的力量，然后跳到第 $4$ 格获胜。这总是可行的，因为在该步开始时棋子位于第 $2$ 或第 $3$ 格，其力量至少可以增加到 $2$。