对于由非负整数组成的多重集 $$$T$$$,我们定义:
- $$$\text{sum}(T)$$$ 是 $$$T$$$ 中所有元素的总和。例如,如果 $$$T = \{0,1, 1, 3\}$$$,则 $$$\text{sum}(T)= 0+1+1+3=5$$$。
- $$$\text{mex}(T)$$$ 是不在 $$$T$$$ 中的最小非负整数。例如,如果 $$$T = \{0,1, 1, 3\}$$$,则 $$$\text{mex}(T) = 2$$$,因为 $$$2$$$ 是 $$$T$$$ 中不存在的最小非负整数。
- 选择子集 $$$S' \subseteq S$$$(即 $$$S'$$$ 包含 $$$S$$$ 中当前的一些元素),将 $$$\text{sum}(S')$$$ 添加到您的分数,然后从 $$$S$$$ 中删除 $$$S'$$$。
- 选择子集 $$$S' \subseteq S$$$,将 $$$\text{mex}(S')$$$ 添加到您的分数中,然后从 $$$S$$$ 中删除 $$$S'$$$。
找出可以获得的最大可能分数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$S_1, S_2, \ldots, S_n$$$ ($$$0 \le S_i \le 50$$$)。
输出
对于每个测试用例,打印一个整数 - 可以获得的最大可能分数。
示例
输入复制
230 1 131 2 3
输出复制
3 6
注意
在第一个测试用例中,可能的最优策略如下:
- 选择 $$$S'=\{0,1\}$$$,将 $$$\text{mex}(S')=\text{mex}(\{0,1\})=2$$$ 添加到您的乐谱中,然后从 $$$S$$$ 中删除 $$$S'$$$。目前,您的分数为 $$$2$$$ 且 $$$S=\{1\}$$$。
- 选择 $$$S'=\{1\}$$$,将 $$$\text{sum}(S')=\text{sum}(\{1\})=1$$$ 添加到您的分数中,然后从 $$$S$$$ 中删除 $$$S'$$$。目前,您的分数为 $$$3$$$ 且 $$$S=\varnothing$$$。
之后,您将无法进行任何进一步的操作。可以证明$$$3$$$是可以获得的最大可能分数。