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?
输入解释
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$.
输出解释
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$.
Hint
In the first test case, one of the best matches is $(2,1,4,3)$. Therefore the answer is $(1 \oplus 2) + (2 \oplus 1) + (3 \oplus 4) + (4 \oplus 3) = 20$.