Mandy has discovered two interesting sequences of length $n$, denoted as $a$ and $b$. She defines the "boredom" of a sequence as the XOR sum of all its elements.

She wants these two sequences to be as interesting as possible; specifically, she wants the more "bored" sequence to be as interesting as possible. She believes that swapping elements at corresponding positions between the two sequences is harmless, and she can perform this operation any number of times.

Now, she wants to know: in the most interesting scenario, what is the boredom of the more bored sequence?

Formally, you have two sequences $a$ and $b$ of length $n$. You can perform any number of operations where you choose an index $i$ ($1 \le i \le n$) and swap $a_i$ and $b_i$. You want to minimize $\max\{f(a), f(b)\}$, where for any sequence $A$, $f(A) = \bigoplus_{i=1}^n A_i$ ($\oplus$ denotes bitwise XOR).

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case: The first line contains an integer $n$ ($1 \le n \le 10^6$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{31}$). The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < 2^{31}$).

It is guaranteed that for all test cases, $\sum n \le 10^6$.

Output

For each test case, output a single integer representing the minimum $\max\{f(a), f(b)\}$.

Examples

Input 1

2
1
1
2
2
1 2
2 1

Output 1

2
0