给定一个整数数组 $$$a$$$,大小为 $$$n$$$。您可以选择给定数组的一组不重叠的子数组(请注意,某些元素可能不包含在任何子数组中,这是允许的)。对于每个选定的子数组,计算其元素的 MEX,然后计算所有获得的 MEX 值的按位异或。可以获得的最大按位异或是多少?
数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:
- $$$[2,2,1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3,1,0,1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0,3,1,2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于数组,但 $$$4$$$ 不属于该数组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$) — 数组 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$) — 数组 $$$a$$$。
保证所有测试用例中所有 $$$n$$$ 值的总和不超过 $$$5000$$$。
输出
对于每个测试用例,输出一个数字 — 所选子数组的 MEX 值的最大可能异或。
示例
输入 #1
4 2 1 0 10 1 2 0 7 1 2 0 2 4 3 10 2 1 0 7 1 2 0 2 4 3 3 1 2 1
输出 #1
2 6 7 0
注意
在第一个测试用例中,如果我们采用整个数组 $$$\operatorname{MEX}([1, 0]) = 2$$$,则最大 XOR 为 $$$2$$$。
在第二个测试用例中,如果我们将数组分为 $$$[1, 2, 0]$$$ 和 $$$[7, 1, 2, 0, 2, 4, 3]$$$ 段,则最大 XOR 为 $$$6$$$:
- $$$\操作员名称{MEX}([1, 2, 0]) = 3$$$,
- $$$\操作员名称{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,
在第三个测试用例中,如果我们将数组分为 $$$[1, 0]$$$ 和 $$$[7, 1, 2, 0, 2, 4, 3]$$$ 段,则最大 XOR 为 $$$7$$$:
- $$$\operatorname{MEX}([1, 0]) = 2$$$,
- $$$\操作员名称{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,