每一个好的题目集都需要一个可以用单个“Doge”表情包概括的问题。今天的题目集也不例外。

给定一个非负整数构成的多重集 $S$，将其划分为两个多重集 $A$ 和 $B$，使得 $|\text{xor}(A) - \text{xor}(B)|$ 最小。其中 $\text{xor}(X)$ 表示集合 $X$ 中所有元素的按位异或和。

注意，多重集 $A$ 和 $B$ 中的一个可以为空，空集的异或和为 $0$。

你只需要输出 $|\text{xor}(A) - \text{xor}(B)|$ 的最小值。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 50$)。接下来是各测试用例的描述，每个测试用例占两行。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示多重集的大小。

第二行包含 $n$ 个整数 $x_i$ ($0 \le x_i \le 10^{18}$)，表示多重集中的元素。

输出格式

对于每个测试用例，输出一个整数：异或和之差的最小值。

样例

样例输入 1

2
4
1 2 3 4
5
3 7 3 9 5

样例输出 1

4
5