Little Cyan Fish is playing Slay the Spire II and has chosen the character "Silent".

Little Cyan Fish now needs to battle a "Battle Friend". Initially, both the Battle Friend's "Poison" stacks and your "Accelerant" level are $0$. In each of the next $n$ turns, the following events occur in order:

1. Play "Deadly Poison": increase the Battle Friend's Poison stacks by $x_i$.

2. Choose whether to play "Accelerant": choose whether to increase your Accelerant level by $1$.

3. Trigger Poison effect: let your Accelerant level be $t$, and repeat the following event $t$ times:

   • Let the Battle Friend's Poison stacks be $x$. If $x > 0$, deal $x$ damage to the Battle Friend and decrease the Poison stacks by $1$; otherwise, if $x = 0$, nothing happens.

Note that both Poison stacks and the Accelerant level carry over across turns and do not disappear.

Little Cyan Fish wants to maximize the total damage dealt to the Battle Friend over these $n$ turns. Please output this maximum damage.

Input

The input contains multiple test cases. The first line of input contains an integer $T$ ($1 \le T$), denoting the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 5000$).

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), denoting the number of Poison stacks added to the Battle Friend in each turn.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, and the sum of $n^2$ over all test cases does not exceed $10^8$.

Output

For each test case, output a single line containing an integer denoting the maximum total damage that can be dealt to the Battle Friend over all turns.

Example

Input 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

Output 1

33
11
750
725