一个叫 Smilo 的男孩正在玩一个新游戏!游戏中,有 $$$n$$$ 群怪物,第 $$$i$$$ 群包含 $$$a_i$$$ 怪物。游戏的目标是消灭所有怪物。为此,您有两种类型的攻击和一个组合计数器 $$$x$$$,最初设置为 $$$0$$$:
- 第一种:你从$$$1$$$到$$$n$$$中选择一个数字$$$i$$$,使得部落中至少剩下一个数字为$$$i$$$的怪物。然后,你从部落编号 $$$i$$$ 中杀死一只怪物,组合计数器 $$$x$$$ 增加 $$$1$$$。
- 第二种:你从$$$1$$$到$$$n$$$中选择一个数字$$$i$$$,这样部落中至少还剩下$$$x$$$个编号为$$$i$$$的怪物。然后,你使用终极攻击并杀死部落中编号为 $$$i$$$ 的 $$$x$$$ 怪物。之后,$$$x$$$ 重置为零。
你的任务是消灭所有怪物,这意味着任何怪物群中都不应该剩下任何怪物。斯米洛希望尽快获胜,因此他希望以最少的攻击次数赢得比赛。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个输入数据集的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 怪物群的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每个部落中的怪物数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot {10^5}$$$。
输出
对于每个测试用例,输出杀死所有怪物所需的最小攻击次数。
示例
输入 #1
4 4 1 3 1 1 4 1 2 1 1 6 3 2 1 5 2 4 2 1 6
输出 #1
4 4 11 5
注意
在第一个测试用例中,我们可以对 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 部落使用第一种类型的攻击,然后使用第二种类型的攻击来消灭 $$$2$$$-nd 部落。我们总共需要 $$$4$$$ 攻击。
在第二个测试用例中,我们可以对$$$1$$$-st和$$$3$$$-rd部落使用第一种类型的攻击,然后使用第二种类型的攻击来消灭$$$2$$$-nd部落,然后对$$$4$$$-th部落使用第一种类型的攻击。我们总共需要 $$$4$$$ 攻击。
在第四个测试用例中,我们可以对$$$1$$$-st部落使用第一种类型的攻击一次,对$$$2$$$-nd部落使用两次,然后对$$$2$$$-nd部落使用第二种类型的攻击,最后使用第一种类型的攻击来消灭$$$2$$$-nd部落。我们总共需要 $$$5$$$ 攻击。