给定一个包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$。

设变量 $m$ 初始化为 $0$，Jellyfish 将执行 $n$ 次以下操作：

• 选择一个下标 $i$ ($1 \leq i \leq |a|$) 并从 $a$ 中删除 $a_i$。
• 将 $\operatorname{MEX}(a)^{\dagger}$ 加到 $m$ 中。

现在 Jellyfish 想知道，如果他以最优方式执行所有操作，最终 $m$ 的最小值是多少。

$^{\dagger}$ 数组的 MEX（最小排斥值）是指数组中不存在的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 都在数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0, 1, 2, 3$ 都在数组中，但 $4$ 不在。

Input

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 5000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 5000$)，表示数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$)，表示数组中的整数。

保证所有测试用例的 $n$ 之和不超过 $5000$。

Output

对于每个测试用例，输出一个整数，表示最优操作下 $m$ 的最小值。

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

在第一个测试用例中，我们按以下顺序从 $a$ 中删除元素：$[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 [~]$。$m$ 的值将为 $1+1+1+0+0+0+0+0=3$。