19245번 - XOR 다국어

문제

Every good problemset needs a problem that can be summarized in a single doge meme. Today's problemset is no different.

Given a multiset $S$ of non-negative integers, divide it into two multisets $A$ and $B$ in a way that minimizes $|\text{xor}(A) - \text{xor}(B)|$. Here $\text{xor}(X)$ denotes the bitwise XOR of all elements of $X$.

Note that one of the multisets $A$ and $B$ can be empty, and XOR of an empty multiset is 0ドル$.

It is enough to output the minimum possible value of $|\text{xor}(A) - \text{xor}(B)|$.

입력

The first line of input contains the number of test cases $z$ (1ドル \leq z \leq 50$). The descriptions of the test cases follow, two lines per test case.

The first line of every test case contains an integer $n$ (1ドル \leq n \leq 10^5$) -- the size of the multiset.

The second line contains $n$ integers $x_i$ (0ドル \leq x_i \leq 10^{18}$) -- elements of the multiset.

출력

For each test case output one integer: the smallest possible difference of XORs.

제한

힌트