A. MEX Game 1
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play yet another game on an array $$$a$$$ of size $$$n$$$. Alice starts with an empty array $$$c$$$. Both players take turns playing, with Alice starting first.

On Alice's turn, she picks one element from $$$a$$$, appends that element to $$$c$$$, and then deletes it from $$$a$$$.

On Bob's turn, he picks one element from $$$a$$$, and then deletes it from $$$a$$$.

The game ends when the array $$$a$$$ is empty. Game's score is defined to be the MEX$$$^\dagger$$$ of $$$c$$$. Alice wants to maximize the score while Bob wants to minimize it. Find game's final score if both players play optimally.

$$$^\dagger$$$ 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 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

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$).

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

Output

For each test case, find game's score if both players play optimally.

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

In the first test case, a possible game with a score of $$$2$$$ is as follows:

  1. Alice chooses the element $$$1$$$. After this move, $$$a=[0,0,1]$$$ and $$$c=[1]$$$.
  2. Bob chooses the element $$$0$$$. After this move, $$$a=[0,1]$$$ and $$$c=[1]$$$.
  3. Alice chooses the element $$$0$$$. After this move, $$$a=[1]$$$ and $$$c=[1,0]$$$.
  4. Bob chooses the element $$$1$$$. After this move, $$$a=[\,]$$$ and $$$c=[1,0]$$$.

At the end, $$$c=[1,0]$$$, which has a MEX of $$$2$$$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.