Cafe Satori 只雇佣经验丰富的服务员，这是有原因的。每天午餐时间，即中午 12:00，一大群饥肠辘辘的顾客进入咖啡馆等待服务。因此，唯一值班的服务员忙得不可开交。幸运的是，他英勇的工作将获得丰厚的小费作为回报。

每位顾客都愿意支付一定数额的小费，前提是他们能立即得到服务。每等待一分钟，小费就会减少 1，直到减为 0。

服务员为一位顾客提供服务需要一分钟。请解决服务员的问题，并计算在最优服务顺序下，他总共能获得多少小费。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 10^9$)。接下来是各测试用例的描述。

每个测试用例的第一行包含顾客数量 $n$ ($1 \le n \le 100\,000$)。第二行包含 $n$ 个不超过 $10^9$ 的非负整数：这些是顾客最初愿意支付的小费金额。

所有测试用例中顾客的总数不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出服务员能获得的最大总小费金额。

样例

样例输入 1

1
6
0 9 9 1 7 5

样例输出 1

24