小科和小中在玩一个取石子的游戏。

游戏开始时有 $n$ 堆石子，第 $i$ 堆石头有 $a_i$ 个石头。小中和小科轮流取石头。小科先手取石子。每一轮可以选择一个非空堆的石堆取出一块石头。如果没有石头可取了，当前该取石子的玩家就输了；如果玩家取完石子之后出现了两堆数量相同的石堆，玩家也被认定输掉。

例如 $n=3$ 的情况，$a_0 = 2，a_1 = 3, a_2 = 0$。很显然我们没有办法从空的石堆里面取出石子，所以先手的小科只剩下两种选择：从第一堆取或者第二堆取。如果取第一堆，石堆情况将变成 [1,3,0]，游戏依旧可以继续。但是如果小科选择了拿第二堆石头，石堆情况将变成 [2,2,0] 小科直接输掉了游戏。所以小科这一轮只能选择第一堆。

在小科和小中都足够聪明的情况下，请问谁会获得游戏的胜利？

需要注意，当游戏开始时如果有两堆石子数量相同，并不能算作小科输掉了，只要小科拿完石子之后不存在两堆石子数量相同，那么游戏继续。

输入

多组输入，第一行一个整数 $t$，表示测试数据组数。

接下来 $t$ 组数据，每组数据两行：

第一行一个整数，表示石子的堆数。

第二行 $n$ 个整数。

输出

输出 $t$ 行，每行一个整数 1 或者 0。

如果小科胜出则输出 0，小中胜出则输出 1。

1
2
1 0

1

提示

$1 \leq T \leq 20$

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^9$