背景

试题来自 清华大学学生算法协会。

题目描述

诺尔有 $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$。

输出格式

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

4
4
1 2 3 1
6
4 7 5 2 6 3
4
14 15 9 18
2
251508091405 13011908091815

2
6
26
13121614001578

提示

对于第一个测试用例，一种可能的划分方法是 $[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 完成