B. Mex Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$2*n$$$ grid $$$a$$$. On the grid,there is a non-negative integer $$$a_{i,j}$$$ in row $$$i$$$ and line $$$j$$$.

You must walk from $$$(1,1)$$$ to $$$(2, n)$$$. Each cell can be accessed at most once.At each step, you can go up, down, or right(but not to the left or beyond the boundary).

Note the set of numbers on the grid you have walked through is $$$S$$$. Find the biggest $$$mex (S)$$$ you can get.

Remember that $$$mex(S)$$$ is the smallest non-negative integer that does not belong to $$$S$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of three line of input.

The first line contains an integer $$$n(1 \leq n \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_{1,1},a_{1,2},...a_{1,n}(0 \leq a_{1,i} \leq 2n)$$$.

The third line contains $$$n$$$ integers $$$a_{2,1},a_{2,2},...a_{2,n}(0 \leq a_{2,i} \leq 2n)$$$.

The sum of $$$n$$$ over all will not exceed $$$10^5$$$.

Output

For each test case,output on a new line — the biggest $$$mex (S)$$$ you can get.

Example
Input
2
3
2 0 2
1 2 1
4
1 0 5 2
3 5 4 1
Output
3
4
Note

Test case $$$1$$$:

$$$(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3)$$$

$$$S=\{0,1,2 \},mex(S)=3$$$.It can be shown that $$$3$$$ is the maximum.

Test case $$$2$$$:

$$$(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,4) \rightarrow (2,4)$$$

$$$S=\{0,1,2,3,5 \},mex(S)=4$$$.It can be shown that $$$4$$$ is the maximum.