题目描述

你在与一个血量未知的 Boss 战斗。你拥有 $n$ 张法术卡牌，其中第 $i$ 张卡牌能造成 $a_i$ 点伤害。你可以任意重新排列并按你选择的顺序打出这些卡牌。

Boss 拥有一个适应性护盾。如果你在战斗中连续打出了两张造成伤害完全相同的卡牌，护盾就会永久激活。触发护盾的那张卡牌仍然会造成正常的伤害，但在那之后你打出的所有卡牌都将造成 $0$ 点伤害。

请计算：在采取最优出牌顺序的情况下，你最多能造成多少总伤害？（这等价于你能确保击败的 Boss 的最大总血量）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 50$）—— 法术卡牌的数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 1000$）—— 表示每张卡牌造成的伤害值。

输出格式

对于每个测试用例，输出一行一个整数，表示你能造成的最大总伤害。

样例输入 1

4
1
100
4
10 5 10 10
5
1 2 3 4 5
6
7 7 7 7 7 7

样例输出 1

100
35
15
14

说明

样例解释

• 在第一个测试用例中，你只有 $1$ 张卡牌。打出它，造成 $100$ 点伤害。
• 在第二个测试用例中，你可以将手牌排列为 $[10, 5, 10, 10]$。你依次打出第一张 $10$，接着打出 $5$，然后打出第二张 $10$，最后打出最后一张 $10$。因为你连续打出了两张 $10$，护盾被激活。然而，触发护盾的卡牌仍然造成正常伤害。造成的总伤害为 $10 + 5 + 10 + 10 = 35$。
• 在第三个测试用例中，所有的卡牌伤害互不相同。你可以按任意顺序打出它们并造成所有的伤害：$1 + 2 + 3 + 4 + 5 = 15$。
• 在第四个测试用例中，所有 $6$ 张卡牌造成的伤害都是 $7$。无论你以什么顺序打出它们，你的第二张卡牌必定与第一张相同。第二张卡牌将触发护盾并造成正常伤害，但剩下的 $4$ 张卡牌造成的伤害均为 $0$。造成的总伤害为 $7 + 7 = 14$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 100$。
• 对于每个测试用例，保证 $1 \le n \le 50$。
• 对于每个测试用例，保证 $1 \le a_i \le 1000$。
• 保证所有的输入数值均为整数。