Background

The input size of this problem is large. Please use a fast input method.

Problem Description

Given a sequence $a$ of length $n$, let $f(a,x)$ be $\operatorname{mex}(a_1\oplus x,a_2\oplus x,\ldots,a_n\oplus x)^{\dagger}$. Find $\min_{x=0}^{\infty}(x+f(a,x))$. Here, $\oplus$ denotes the bitwise XOR operation.

$^\dagger$ For natural numbers $x_1,x_2\ldots,x_n$, $\operatorname{mex}(x_1,x_2,\ldots,x_n)$ denotes the smallest non-negative integer that does not appear among $x_1,x_2,\ldots,x_n$.

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ numbers, representing the sequence $a$.

Output Format

For each test case, output one line with one number, representing the answer.

3
5
1 4 5 2 6
6
0 1 4 5 2 6
3
0 1 3

0
3
2

Hint

[Sample Explanation]

For the first test case, take $x=0$, then $f(a,0)=\operatorname{mex}(1,4,5,2,6)=0$. Obviously, there cannot be an answer smaller than $0$.

For the second test case, take $x=1$, then $f(a,1)=\operatorname{mex}(1,0,5,4,3,7)=2$. It can be proven that $3$ is the minimum value of $x+f(a,x)$.

[Constraints]

For all testdata, it is guaranteed that:

• $1\le T\le 20$;
• $1\le n\le 10^6$;
• $\forall i\in[1,n],0\le a_i<2^{30}$.

The special properties of each test point are as follows:

Translated by ChatGPT 5