M. Asem hates Moon's EX (Pink)
time limit per test
2 s.
memory limit per test
256 MB
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers.

You must choose exactly one integer $$$X (0 \le X \le 10^9)$$$ and apply the following operation once: replace every element $$$a_i$$$ with $$$a_i$$$ $$$\oplus$$$ $$$X$$$ (the character $$$\oplus$$$ denotes bitwise $$$XOR$$$).

After performing this operation, let the resulting array be $$$b$$$. Your task is to determine the maximum possible $$$MEX$$$ of the array $$$b$$$.

The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$
Input

The first line contains an integer $$$t (1 \le t \le 10^4)$$$ — denotes the number of test cases.

The first line of each test case contains a single integer $$$n (1 \le n \le 2 \cdot 10^5)$$$ — denotes the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n(0 \le a_i \le 10^6)$$$ — denotes the array elements.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case print a single integer, the maximum $$$MEX$$$ that can be obtained after applying the operation exactly once.

Example
Input
3
2
1 0
4
1 1 7 10
5
1 2 3 4 5
Output
2
1
3