Alice 和 Bob 正在玩一个改进版的 Nim 游戏。初始时，他们面前有一些非空的石子堆。两人轮流进行操作，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 先手，且双方均采取最优策略。按输入中游戏的顺序输出结果。

样例

输入 1

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

输出 1

0
1
0
1