白板上写着 $$$2n$$$ 个正整数。由于无聊,您决定用白板上的数字玩一个单人游戏。
您的起始分数为 $$$0$$$。通过精确执行以下动作 $$$n$$$ 次,您将提高分数:
- 选择写在白板上的两个整数 $$$x$$$ 和 $$$y$$$。
- 将 $$$\min(x,y)$$$ 添加到您的分数中。
- 从白板上擦除 $$$x$$$ 和 $$$y$$$。
请注意,执行移动 $$$n$$$ 次后,白板上将不再写入任何整数。
找出如果您以最佳方式执行 $$$n$$$ 动作,您可以获得的最高最终分数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) - 白板上写的整数数量是 $$$2n$$$。
每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \leq a_i \leq 10^7$$$) - 白板上写的数字。
输出
对于每个测试用例,输出您可以获得的最高最终分数。
示例
输入 #1
3 1 2 3 2 1 1 2 1 3 1 1 1 1 1 1
输出 #1
2 2 3
注意
在第一个测试用例中,您只能移动一步。您选择$$$x=2$$$ 和$$$y=3$$$,您的分数将为$$$\min(x,y)=2$$$。
在第二个测试用例中,以下是最终得分为 $$$2$$$ 的一系列移动:
- 在第一步中,选择 $$$x=1$$$ 和 $$$y=1$$$。然后,将 $$$\min(x,y)=1$$$ 添加到分数中。擦掉$$$x$$$和$$$y$$$后,白板上剩下的整数是$$$1$$$和$$$2$$$。
- 在第二步中,选择 $$$x=1$$$ 和 $$$y=2$$$。然后,将 $$$\min(x,y)=1$$$ 添加到分数中。删除 $$$x$$$ 和 $$$y$$$ 后,白板上将不再留下任何整数。
在第三个测试用例中,您将执行三次移动,每次将 $$$1$$$ 添加到分数中。