Statement : D. Palindromex

Yousef has given you an array $a$ of $2n$ integers. Every integer $x \in [0, n - 1]$ appears exactly twice in the array.

Your task is to find a subarray $a_l, a_{l + 1}, \dots, a_r$ that is a palindrome$^{\text{∗}}$ such that its $\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$$^{\text{†}}$ is maximized. Output this maximum possible value.

$^{\text{∗}}$A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

$^{\text{†}}$The $\operatorname{mex}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:

• The $\operatorname{mex}$ of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The $\operatorname{mex}$ of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The $\operatorname{mex}$ of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($0 \le a_i \le n-1$). It is guaranteed that every integer in the range $[0, n-1]$ appears exactly twice.

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

For each test case, output a single integer — the maximum $\operatorname{mex}$ of any palindromic subarray.

Input

6
4
1 2 0 3 3 0 2 1
2
0 1 0 1
2
1 1 0 0
3
2 0 2 1 1 0
4
0 1 3 0 3 1 2 2
3
0 1 2 1 0 2

Output

4
2
1
1
2
3

Note

In the first test case, the only optimal subarray to choose is $a[1, 8] = [1, 2, 0, 3, 3, 0, 2, 1]$, which is palindromic and has a $\operatorname{mex}$ of $4$.

In the second test case, one of the optimal subarrays to choose is $a[2, 4] = [1, 0, 1]$, which is palindromic and has a $\operatorname{mex}$ of $2$.

In the third test case, we can choose $a[3, 3] = [0]$, which is palindromic and has a $\operatorname{mex}$ of $1$. No other palindromic subarray has a $\operatorname{mex}$ greater than $1$.