小蓝鱼（Little Cyan Fish）被雇佣来测试又一款塔防游戏。工作室坚持认为游戏已经几乎可以出货了，尽管 Boss 仍然沿着一条完全笔直的直线行走，防御塔只能放置在整数坐标上，而且 Boss 的护盾对战场上最右侧的防御塔产生了极具针对性的怨念。

准备部署防御塔。

战场由数轴表示。有 $n$ 个防御塔可供部署。第 $i$ 个防御塔具有 $a_i$ 单位的能量，且最多只能部署一次。部署防御塔意味着选择一个未被占用的整数坐标并在该处放置一个防御塔。能量为正的防御塔是活跃的；一旦其能量变为 0，它就会从战场上消失。这在手册中被称为自动清理。

游戏按回合进行。在每个回合中，依次发生以下事件：

1. 小蓝鱼选择以下两个选项之一：在数轴上的一个空闲整数坐标处部署一个此前未部署的防御塔，或者什么都不做。
2. 每个已部署且能量为正的防御塔对 Boss 造成 1 点伤害。
3. 在所有已部署且能量为正的防御塔中，坐标最大的防御塔会被 Boss 诅咒并失去 1 点能量。如果该防御塔的能量降至 0，它将从防线中消失。

模拟器被配置为运行前 $9^{9^9}$ 回合，因为有人在设置面板中输入了这个数字，而没有人想去动生产环境的代码。请帮助小蓝鱼求出可以对 Boss 造成的最大总伤害。

输入格式

每个输入文件包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示最大总伤害。

样例

输入样例 1

4
3
3 1 1
3
2 2 2
4
4 5 6 7
3
123456789 987654321 998244353

输出样例 1

9
12
60
5093498490

说明

样例 1 说明：在坐标 0 处放置一个能量为 3 的防御塔，然后依次在坐标 -1 和 -2 处放置能量为 1 的防御塔。