D. Palindromex

Yousef has given you an array 𝑎

 of 2𝑛

 integers. Every integer 𝑥∈[0,𝑛−1]

 appears exactly twice in the array.

Your task is to find a subarray 𝑎

𝑙

,𝑎

𝑙+1

,…,𝑎

𝑟

 that is a palindrome

∗

 such that its mex(𝑎

𝑙

,𝑎

𝑙+1

,…,𝑎

𝑟

)

†

 is maximized. Output this maximum possible value.

∗

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.

†

The 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 mex
•  of [2,2,1]
•  is 0
• , because 0
•  does not belong to the array.
• The mex
•  of [3,1,0,1]
•  is 2
• , because 0
•  and 1
•  belong to the array, but 2
•  does not.
• The mex
•  of [0,3,1,2]
•  is 4
• , because 0
• , 1
• , 2
•  and 3
•  belong to the array, but 4
•  does not.

Input

The first line contains a single integer 𝑡

 (1≤𝑡≤10

4

) — the number of test cases.

The first line of each test case contains a single integer 𝑛

 (1≤𝑛≤10

5

).

The second line of each test case contains 2𝑛

 integers 𝑎

1

,𝑎

2

,…,𝑎

2𝑛

 (0≤𝑎

𝑖

≤𝑛−1

). It is guaranteed that every integer in the range [0,𝑛−1]

 appears exactly twice.

It is guaranteed that the sum of 2𝑛

 over all test cases does not exceed 2⋅10

5

.

Output

For each test case, output a single integer — the maximum mex

 of any palindromic subarray.

Example

Input

Copy

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

Copy

4
2
1
1
2
3

Note

In the first test case, the only optimal subarray to choose is 𝑎[1,8]=[1,2,0,3,3,0,2,1]

, which is palindromic and has a mex

 of 4

.

In the second test case, one of the optimal subarrays to choose is 𝑎[2,4]=[1,0,1]

, which is palindromic and has a mex

 of 2

.

In the third test case, we can choose 𝑎[3,3]=[0]

, which is palindromic and has a mex

 of 1

. No other palindromic subarray has a mex

 greater than 1

.