Jellyfish and Mex
Description
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.
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$.
For each test case, output a single integer — the minimum value of $m$ if the operations are performed optimally.
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.
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
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$.