有一条 $$$n + 1$$$ 单元格,编号从 $$$1$$$ 到 $$$n + 1$$$。最初,单元格号 $$$1$$$ 上有一个具有权力 $$$1$$$ 的令牌,数字 $$$a_1、a_2、\ldots、a_n$$$ 分别写在单元格 $$$1、2、\ldots、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$$$ 迈出第一步。)
示例
输入复制
430 0 031 1 250 0 1 0 090 1 2 0 0 1 0 0 0
输出复制
1212
注意
在第一个测试用例中,代币的力量在整个游戏中保持等于 $$$1$$$,因此玩家的每一步都必须向前移动一个单元格。因此,将进行 $$$3$$$ 步,最后一步将由玩家 $$$1$$$ 进行,因此无论如何他都会获胜。
在第二个测试用例中,玩家 $$$2$$$ 有一个获胜策略:在第一步中,尽可能增加代币的力量,然后跳转到单元格 $$$4$$$ 并获胜。这总是可能的,因为在移动开始时,代币将位于单元格 $$$2$$$ 或 $$$3$$$ 上,并且其功率可以增加到至少 $$$2$$$。