codeforces#P1870E. Another MEX Problem

Another MEX Problem

Description

You are given an array of integers aa of size nn. You can choose a set of non-overlapping subarrays of the given array (note that some elements may be not included in any subarray, this is allowed). For each selected subarray, calculate the MEX of its elements, and then calculate the bitwise XOR of all the obtained MEX values. What is the maximum bitwise XOR that can be obtained?

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of [2,2,1][2,2,1] is 00, because 00 does not belong to the array.
  • The MEX of [3,1,0,1][3,1,0,1] is 22, because 00 and 11 belong to the array, but 22 does not.
  • The MEX of [0,3,1,2][0,3,1,2] is 44, because 00, 11, 22 and 33 belong to the array, but 44 does not.

The first line contains an integer tt (1t50001 \leq t \leq 5000) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains an integer nn (1n50001 \leq n \leq 5000) — the size of the array aa.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ain0 \leq a_i \leq n) — the array aa.

It is guaranteed that the sum of all nn values across all test cases does not exceed 50005000.

For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

Input

The first line contains an integer tt (1t50001 \leq t \leq 5000) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains an integer nn (1n50001 \leq n \leq 5000) — the size of the array aa.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ain0 \leq a_i \leq n) — the array aa.

It is guaranteed that the sum of all nn values across all test cases does not exceed 50005000.

Output

For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

输入数据 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

Note

In the first test case, the maximum XOR is 22 if we take the entire array, MEX([1,0])=2\operatorname{MEX}([1, 0]) = 2.

In the second test case, the maximum XOR is 66 if we partition the array into segments [1,2,0][1, 2, 0] and [7,1,2,0,2,4,3][7, 1, 2, 0, 2, 4, 3]:

  • MEX([1,2,0])=3\operatorname{MEX}([1, 2, 0]) = 3,
  • MEX([7,1,2,0,2,4,3])=5\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5,
therefore, the XOR is 53=65 \oplus 3=6.

In the third test case, the maximum XOR is 77 if we partition the array into segments [1,0][1, 0] and [7,1,2,0,2,4,3][7, 1, 2, 0, 2, 4, 3]:

  • MEX([1,0])=2\operatorname{MEX}([1, 0]) = 2,
  • MEX([7,1,2,0,2,4,3])=5\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5,
therefore, the XOR is 52=75 \oplus 2 = 7.