题目描述

给定一个初始包含 $n$ 个非负整数的数组 $a$。

你将执行恰好 $n-1$ 次以下操作：

1. 从当前数组 $a$ 中选择一个下标 $i$（$1 \le i \le |a|$，其中 $|a|$ 表示当前数组的长度），并令 $x = a_i$。
2. 将当前数组中所有的元素 $a_j$（$1 \le j \le |a|$）赋值为 $a_j \oplus x$，其中 $\oplus$ 表示按位异或运算。
3. 将选中的元素 $a_i$ 从数组中删除（此时被删除元素的值为 $x \oplus x = 0$）。

可以证明，经过 $n-1$ 次操作后，数组中将恰好剩下唯一一个元素。你的任务是找出，在采取最优操作顺序的情况下，这最后一个剩余元素可能达到的最大值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 3105$）—— 数组初始的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）—— 数组初始的元素。

输出格式

对于每个测试用例，输出一行一个整数，表示经过最优操作后最后剩余元素的最大可能值。

样例输入 1

3
2
67 67
3
1 2 3
10
67 667 167 867 267 467 367 567 767 967

样例输出 1

0
3
1012

说明

样例解释

在第二个测试用例中，初始数组为 $[1, 2, 3]$。一种最优的操作序列如下：

1. 选择元素 $3$（令 $x = 3$）。将所有元素异或 $3$ 后删除原先的 $3$。剩余的元素变为 $[1 \oplus 3, 2 \oplus 3] = [2, 1]$。
2. 选择元素 $2$（令 $x = 2$）。将所有元素异或 $2$ 后删除原先的 $2$。剩余的元素变为 $[1 \oplus 2] = [3]$。 最终剩下的值为 $3$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 100$。
• 对于每个测试用例，保证 $2 \le n \le 3105$。
• 对于每个测试用例，保证 $0 \le a_i \le 10^9$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $3105$。
• 保证所有的输入数值均为整数。