#P1875D. Jellyfish and Mex

Jellyfish and Mex

Description

You are given an array of nn nonnegative integers a1,a2,,ana_1, a_2, \dots, a_n.

Let mm be a variable that is initialized to 00, Jellyfish will perform the following operation nn times:

  • select an index ii (1ia1 \leq i \leq |a|) and delete aia_i from aa.
  • add MEX(a)\operatorname{MEX}(a)^{\dagger} to mm.

Now Jellyfish wants to know the minimum possible final value of mm 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][2,2,1] is 00, because 00 does not belong to the array.
  • The MEX of [3,1,0,1][3,1,0,1] is 22, because 00 and 11 belong to the array, but 22 does not.
  • The MEX of [0,3,1,2][0,3,1,2] is 44 because 00, 11, 22, and 33 belong to the array, but 44 does not.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t50001 \leq t \leq 5000). The description of the test cases follows.

The first line of each test case contains a single integer nn (1n50001 \leq n \leq 5000) — the size of the array.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0ai1090 \leq a_i \leq 10^9) — the integers in the array.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000.

For each test case, output a single integer — the minimum value of mm if the operations are performed optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t50001 \leq t \leq 5000). The description of the test cases follows.

The first line of each test case contains a single integer nn (1n50001 \leq n \leq 5000) — the size of the array.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0ai1090 \leq a_i \leq 10^9) — the integers in the array.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000.

Output

For each test case, output a single integer — the minimum value of mm if the operations are performed optimally.

Sample 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

Sample Output 1

3
0
2
7

Note

In the first test case, we delete elements from aa in the following order: [5,2,1,0,3,0,4,0][5,2,0,3,0,4,0][5,2,0,3,4,0][5,2,3,4,0][5,2,3,4][5,2,4][2,4][4][ ][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 mm will be 1+1+1+0+0+0+0+0=31+1+1+0+0+0+0+0=3.