P16080 [ICPC 2023 NAC] Splitting Pairs

Alice 和 Bob 正在玩一个修改版的尼姆游戏。初始时，他们面前有若干堆非空的石子。两人轮流操作，Alice 先手。 在每一回合中，玩家必须按顺序执行以下操作： - 移除一定数量的石子堆——至少移除 1 堆，但不能超过当前堆数的一半。 - 从剩余的石子堆中，选择同样数量的堆，并将其中每一堆都拆分成两个非空的堆。 注意，每次合法操作后，非空石子堆的数量应与游戏开始时相同。无法在回合中完整执行所有操作的玩家输掉游戏。 你会得到多局游戏，对于每局游戏，你需要判断在双方都采取最优策略的情况下，哪一方会获胜。

输入的第一行包含一个整数 $ t $（$ 1 \le t \le 1{,}000 $），表示 Alice 和 Bob 进行的游戏局数。 每局游戏由两行表示。每局游戏的第一行包含一个整数 $ n $（$ 2 \le n \le 50 $），表示石子堆的数量。 该局游戏的下一行包含 $ n $ 个空格分隔的整数 $ s $（$ 1 \le s \le 10^{12} $），表示每堆石子的数量。

输出 $ t $ 行。对于每局游戏，输出一行一个整数，如果 Alice 获胜则输出 $ 1 $，如果 Bob 获胜则输出 $ 0 $。假设 Alice 先手，且双方均采取最优策略。按输入顺序输出每局游戏的结果。

翻译由 DeepSeek V3.2 完成