Problem Description

People in love always feel humble. Sometimes, Rikka is worried about whether she deserves love from Yuta.

Stable marriage problem is an interesting theoretical model which has a strong connection with the real world. Given $n$ men and $n$ women, where each person has ranked all members of the opposite sex in order of preference. We use a permutation $p$ of length $n$ to represent a match that the $i$th man gets married with the $p_i$th woman. A match is stable if and only if there are no two people of opposite sexes who would both rather have each other than their current partners, i.e., $\forall i \neq j, \neg (r_i(p_j,p_i) \wedge r_{p_j}(i,j))$ where $r_a(b,c)$ represents whether person $a$ loves $b$ more than $c$.

Rikka wants to resolve the confusion in her mind by considering a special case of the stable marriage problem. Rikka uses a feature integer to represents a person's character, and for two persons with feature integers equal to $x$ and $y$, Rikka defines the suitable index of them as $x \oplus y$, where $\oplus$ represents binary exclusive-or.

Given $n$ men with feature integers $a_1, \dots, a_n$ and $n$ women with feature integers $b_1, \dots, b_n$. For the $i$th man, he loves the $j$th woman more than the $k$th woman if and only if $a_i \oplus b_j > a_i \oplus b_k$; for the $i$th woman, she loves the $j$th man more than the $k$th man if and only if $b_i \oplus a_j > b_i \oplus a_k$.

Rikka wants to calculate the best stable match for this problem, i.e., let $\mathbb P$ be the set of all stable match, she wants to calculate $\max_{p \in \mathbb P} \left(\sum_{i=1}^n \left(a_i \oplus b_{p_i} \right) \right)$. Since $n$ is quite large, this problem is too difficult for Rikka, could you please help her find the answer?

Input

The first line of the input contains a single integer $T(1 \leq T \leq 50)$, the number of test cases.

For each test case, the fisrt line contains a sigle integer $n(1 \leq n \leq 10^5)$.

The second line contains $n$ integers $a_1, \dots, a_n(1 \leq a_i \leq 10^9)$ which represents the feature number of each man.

The third line contains $n$ integers $b_1, \dots, b_n(1 \leq b_i \leq 10^9)$ which represents the feature number of each woman.

The input guarantees that there are no more than $5$ test cases with $n > 10^4$, and for any $i,j \in [1,n], i \neq j$, $a_i \neq a_j$ and $b_i \neq b_j$.

Output

For each test case, output a single line with a single integer, the value of the best stable match. If there is no stable match, output $-1$.

2
4
1 2 3 4
1 2 3 4
5
10 20 30 40 50
15 25 35 45 55

20
289