Background

"Even if we do not look up at the starry sky, it is always watching us."

Problem Description

Countless jellyfish that once traveled with you have turned into tiny starlight and slowly risen into the boundless night sky. They can be represented as $n$ points on an infinitely long number line, where the $i$-th point is initially at $a_i$. Multiple points may be at the same position.

Index wants to perform at most $10^{218105633}$ evolutions on these points (the number of times can be $0$). In one evolution, she will:

1. Choose a position $x$ that currently contains at least two points.
2. Decrease the number of points at $x$ by $2$.
3. Increase the number of points at $x-1$ and $x+1$ by $1$ each.

Index wants to know the maximum possible value of the $\operatorname{mex}$ of the set formed by the positions of all points after the operations finish.

Note: For an integer set $S$, $\operatorname{mex}(S)$ is defined as the smallest non-negative integer that does not belong to $S$.

Input Format

The first line contains an integer $T$, the number of testdata groups.

For each testdata group:

The first line contains an integer $n$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the initial positions of the points.

Output Format

For each testdata group, output one integer per line, representing the maximum $\operatorname{mex}$ that can be achieved.

1
4
1 1 2 2

4

Hint

One possible sequence of operations is:

At this time, the positions of all points are $\{0,1,2,3\}$, and its $\operatorname{mex}$ is $4$. It can be proven that the answer cannot be larger.

Constraints (for all testdata):

$1\le n,\sum n\le 5\times 10^5,0\le a_i\le 10^9$。

::cute-table{tuack}

Special Property A: All $a_i$ are guaranteed to be the same.

Input Format

Output Format

Hint

Translated by ChatGPT 5