给你一个 $$$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$$$ 不属于该数组。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 如果操作执行最佳,则 $$$m$$$ 的最小值。
示例
输入 #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
输出 #1
3 0 2 7
注意
在第一个测试用例中,我们按以下顺序从 $$$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$$$。