题目描述

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 $a$ 和 $b$ ，初始值均为 0。

有一个给定的长度为 $n$ 的公共数列 $X_1,X_2,⋯ ,X_n$ 。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：

选项 1：从数列中选一个 $X_i$ 给 Alice 的数异或上，或者说令 $a$ 变为 $a⊕X_i$ 。（其中 $⊕$ 表示按位异或）

选项 2：从数列中选一个 $X_i$ 给 Bob 的数异或上，或者说令 $b$ 变为 $b⊕X_i$ 。

每个数 $X_i$ 都只能用一次，当所有 $X_i$ 均被使用后（ $n$ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。现在双方都足够聪明，都采用最优策略，请问谁能获胜？

输入描述

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$ ，表示询问数。

接下来 $T$ 行每行包含一组询问。其中第 $i$ 行的第一个整数 $n_i$ 表示数列长度，随后 $n_i$ 个整数 $X_1,X_2,⋯ ,X_{ni}$ 表示数列中的每个数。

输出 $T$ 行，依次对应每组询问的答案。每行包含一个整数 1、0 或 -1 分别表示 Alice 胜、平局或败。

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

对于所有评测用例，$1≤T≤200000，1≤\sum_{i=1}^{T}n_i ≤200000,0≤X_i<20^{20}$。