题目描述

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 先手，且双方均采取最优策略。按输入顺序输出每局游戏的结果。

4
3
1 1 1
3
1 1 2
3
2 2 2
4
4 4 4 4

0
1
0
1

提示

翻译由 DeepSeek V3.2 完成