You are given an array of $n$ nonnegative integers $a_1, a_2, \dots, a_n$.

Let $m$ be a variable that is initialized to $0$, Jellyfish will perform the following operation $n$ times:

• select an index $i$ ($1 \leq i \leq |a|$) and delete $a_i$ from $a$.
• add $\operatorname{MEX}(a)^{\dagger}$ to $m$.

Now Jellyfish wants to know the minimum possible final value of $m$ if he performs all the operations optimally.

$^{\dagger}$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• 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 the number of test cases $t$ ($1 \leq t \leq 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$)~--- the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$)~--- the integers in the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

Output

For each test case, output a single integer~--- the minimum value of $m$ if the operations are performed optimally.

Examples

Input 1

4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3

Output 1

3
0
2
7

Note

In the first test case, we delete elements from $a$ in the following order: $[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$. The value of $m$ will be $1+1+1+0+0+0+0+0=3$.