Bubble XOR Sort

Input

The first line contains one integer $t$ (1 \le t \le 10^{5}) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ (1 \le n \le 2 \cdot 10^{5}) — the number of elements in $a$ and $b$.

The second line of the test case contains $n$ integers a_1, a_2, \dots, a_n (1 \le a_i \le n) — the elements of array $a$.

The third line of the test case contains $n$ integers b_1, b_2, \dots, b_n (1 \le b_i \le n) — the elements of array $b$.

It is guaranteed that the sum of $n$ over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, print one integer — the minimum cost required to transform array $a$ into array $b$.

Examples

Note

In the first test case of the sample initially, a = [1,1,2] and we need to obtain b = [1,2,1].

We can swap the last two elements of $a$ at the cost of 1 \oplus 2 = 3 to make a = [1,2,1]. So, the minimum cost is $3$.

Scoring

1. Subtask $1$ ($20$ points): (\sum n \le 9)

2. Subtask $2$ ($20$ points): (\sum n \le 2000)

3. Subtask $3$ ($30$ points): (a_i \le 2000 for all 1 \le i \le n)

4. Subtask $4$ ($40$ points): (\sum n \le 5 \cdot 10^{4})

5. Subtask $5$ ($40$ points): (elements of $a$ are pairwise distinct)

6. Subtask $6$ ($200$ points): No additional constraints