← 返回题目列表

Codeforces · 2218/E

E. 第67个异或问题

中文机器翻译题面 查看原题

PMOI 甚至没有那么糟糕——坊间流传的说法是,这些问题还不错,甚至(但愿不会)令人愉快!然而,令猕猴沮丧的是,三名不守规矩的参与者(Cloud、ChatGBT 和 Grook)开始利用他们对 OEIS 的完美记忆进行作弊。真是无赖啊!突然间,猕猴必须快速行动,设计出一个让这三个人无法作弊的问题。你从他的同伴降级为他可怜的奴隶,被征召参加测试。

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

您执行以下操作正好 $$$n-1$$$ 次:

  1. 选择 $$$a$$$ 的索引 $$$i$$$($$$1 \leq i \leq |a|$$$,其中 $$$|a|$$$ 表示 $$$a$$$ 的当前长度)。让$$$x = a_i$$$。
  2. 对所有 $$$1 \leq j \leq |a|$$$ 设置 $$$a_j = a_j \oplus x$$$,其中 $$$\oplus$$$ 表示按位异或运算。
  3. 从数组中删除 $$$a_i$$$。

可以看出,经过 $$$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$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3105$$$。

输出

对于每个测试用例,输出一个整数 - 最终元素的最大可能值。

示例

输入
复制

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

输出
复制

0
3
1012

注意

在第二个测试用例中,数组为 $$$[1, 2, 3]$$$。一种最佳操作顺序是:

  1. 选择元素$$$3$$$。将其删除。其余元素变为 $$$[1 \oplus 3, 2 \oplus 3] = [2, 1]$$$。
  2. 选择元素$$$2$$$。将其删除。剩余元素变为 $$$[1 \oplus 2] = [3]$$$。
最终值为 $$$3$$$。