P17127 [ICPC 2025 Shanghai R] Gemcrate

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

诺尔有 $n$ 颗宝石。第 $i$ 颗宝石上写有一个正整数 $a_i$。诺尔想将这些宝石划分成若干个非空的组。每颗宝石恰好属于一个组。 假设第 $i$ 组包含的宝石标号为 $k_{i,1}, k_{i,2}, \ldots, k_{i,p}$，则诺尔将第 $i$ 组的**亮度**定义为 $a_{k_{i,1}} \oplus a_{k_{i,2}} \oplus \cdots \oplus a_{k_{i,p}}$，其中 $\oplus$ 是按位异或运算。记第 $i$ 组的**亮度**为 $B_i$。 对于一个分为 $m$ 组的划分方法，诺尔将该方法的**价值**视为 $B_1 \& B_2 \& \ldots \& B_m$，其中 $\&$ 是按位与运算。 诺尔希望找到所有划分方法中可能的最大**价值**。

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 对于每组测试用例，第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示宝石的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i < 2^{60}$)，即宝石上写的整数。 保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

对于每组测试用例，输出一个整数，表示所有划分方法中可能的最大**价值**。

对于第一个测试用例，一种可能的划分方法是 $[1,2,3,1] = [1,3], [2,1]$，其价值为 $B_1 \& B_2 = (1 \oplus 3) \& (2 \oplus 1) = 2 \& 3 = 2$。另一种可能的划分方法是 $[1,2,3,1] = [1,2,3,1]$，价值较低，为 $B_1 = 1 \oplus 2 \oplus 3 \oplus 1 = 1$。可以证明无法获得大于 $2$ 的价值。 对于第二个测试用例，最佳划分方法是 $[4,7,5,2,6,3] = [7], [5,3], [6], [4,2]$，其价值为 $7 \& (5 \oplus 3) \& 6 \& (4 \oplus 2) = 6$。 翻译由 DeepSeek V4 Pro 完成