小青鱼正在玩《杀戮尖塔 II》（Slay the Spire II），并选择了角色“静默猎手”（Silent）。

小青鱼现在需要与一个战斗伙伴（Battle Friend）进行战斗。初始时，战斗伙伴的“中毒”（Poison）层数和你的“加速剂”（Accelerant）等级均为 $0$。在接下来的 $n$ 回合中，每回合将依次发生以下事件：

1. 使用“致命毒药”（Deadly Poison）：将战斗伙伴的中毒层数增加 $x_i$。

2. 选择是否使用“加速剂”：选择是否将你的加速剂等级增加 $1$。

3. 触发中毒效果：设你的加速剂等级为 $t$，重复以下事件 $t$ 次：

   • 设战斗伙伴的中毒层数为 $x$。如果 $x > 0$，对战斗伙伴造成 $x$ 点伤害，并将中毒层数减少 $1$；否则，若 $x = 0$，什么也不发生。

注意，中毒层数和加速剂等级都会跨回合保留，不会消失。

小青鱼想要最大化在这 $n$ 回合内对战斗伙伴造成的总伤害，请输出该最大伤害值。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$（$1 \le n \le 5000$）。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 \le x_i \le 10^7$），表示每回合战斗伙伴增加的中毒层数。

保证所有测试数据的 $n$ 之和不超过 $10^6$，且所有测试数据的 $n^2$ 之和不超过 $10^8$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示在所有回合中能对战斗伙伴造成的最大总伤害。

样例

输入样例 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

输出样例 1

33
11
750
725