题目描述

题目译自 Ukrainian Olympiads in Informatics 2017 Stage 4 Day1 T2. Гра

两人玩一个游戏。桌上并排摆放着 $N$ 堆火柴。第一位玩家在第一步必须从第一堆火柴中拿走一根。第二位玩家在下一步可以从第一堆或第二堆中取走一根火柴，也可以从这两堆中各取一根。第一位玩家在第三步可以从前三堆中的任意几堆各取一根火柴，但必须至少从一堆中取。然后第二位玩家可以从前四堆中取火柴，以此类推。在第 $N$ 步之后，每位玩家可以从任意几堆中各取一根火柴，但同样必须至少从一堆中取。拿走最后一根火柴的玩家获胜。

请编写一个程序，根据火柴堆的初始数量，判断在最优策略下哪位玩家会获胜。

输入格式

输入数据的第一行包含一个整数 $T$ $(1 \leq T \leq 10)$。

接下来的 $T$ 行包含每组输入数据的描述（每行一个），格式如下：首先是一个整数 $N$ $(1 \leq N \leq 1000)$，然后是 $N$ 个整数，表示各堆火柴的数量。每个数量都不超过 $1000$。

输出格式

输出数据应包含 $T$ 行。每行应包含一个数字：如果在相应输入数据的最优博弈中第一位玩家获胜，则为 $1$；如果第二位玩家获胜，则为 $2$。

3
2
1 1
2
1 2
2
2 1

2
1
2

数据范围与提示

• 对于 $20\%$ 的数据，$T=3$ 且所有 $N=2$，每堆火柴数不超过 $5$。
• 对于 $20\%$ 的数据，$T=3$ 且所有 $N=3$，每堆火柴数不超过 $5$。
• 对于 $20\%$ 的数据，$T=6$ 且所有 $N=3$，每堆火柴数不超过 $6$。