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

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

.

Codeforces Round 1096 (Div. 3)

Round Problems