Migrated from Lutece 3181 mex与xor

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

对于一个长度为n的序列，请你选出任意个不相交的区间，使得这些区间的mex的xor最大。 对于区间[l,r],它的mex为集合$\{a_l,a_l+1,...,a_r\}$中没有出现过的最小非负整数。 两个数的xor是指将两个数表示为二进制形式，对于每一位，如果两个数在这一位相同，xor在这一位的结果为1，否则为0。

Input

第一行一个正整数T，代表数据组数。 每组数据包含两行输入。 第一行一个正整数n，代表序列长度。 第二行n个正整数 ${a_1,...,a_n}$ , 代表序列。

Output

每组数据输出一个非负整数，代表最大的mex之xor。

Samples

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

2
6
7
0

Constraints

1<=T<=5000 1<=n<=5000 0<=$a_i$<=n 保证所有n加起来不超过5000

Note

样例说明： 对于第一组数据： 选择区间[1,2],mex为2，xor和为2 对于第二组数据 选择区间[1,3] 与 [4,10] , [1,3]的mex为3，[4,10] 的 mex 为 5。3 与 5 的 xor 为 6

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming