Little Cyan Fish は『Slay the Spire II』をプレイしており、キャラクター「サイレント」（Silent）を選択しました。

Little Cyan Fish はこれから「バトルフレンド」（Battle Friend）と戦う必要があります。最初、バトルフレンドの「毒」（Poison）の値とあなたの「アクセララント」（Accelerant）のレベルはともに $0$ です。続く $n$ ターンの各ターンにおいて、以下のイベントが順に発生します：

1. 「デッドリーポイズン」（Deadly Poison）を使用する：バトルフレンドの毒の値を $x_i$ 増やす。

2. 「アクセララント」を使用するかどうか選択する：あなたのアクセララントのレベルを $1$ 増やすかどうかを選択する。

3. 毒の効果を発動する：あなたのアクセララントのレベルを $t$ とし、以下のイベントを $t$ 回繰り返す：

   • バトルフレンドの毒の値を $x$ とする。もし $x > 0$ ならば、バトルフレンドに $x$ ダメージを与え、毒の値を $1$ 減らす。そうでなければ、すなわち $x = 0$ のときは何も起こらない。

なお、毒の値とアクセララントのレベルはともにターンをまたいで引き継がれ、消えることはありません。

Little Cyan Fish はこれら $n$ ターンの間にバトルフレンドに与える合計ダメージを最大化したいと考えています。その最大ダメージを出力してください。

入力

入力は複数のテストケースからなる。入力の 1 行目には、テストケースの個数を表す整数 $T$（$1 \le T$）が与えられる。

各テストケースについて、1 行目には整数 $n$（$1 \le n \le 5000$）が与えられる。

2 行目には、各ターンでバトルフレンドに付与される毒の値を表す $n$ 個の整数 $x_1, x_2, \dots, x_n$（$0 \le x_i \le 10^7$）が与えられる。

すべてのテストケースにおける $n$ の総和は $10^6$ 以下であり、すべてのテストケースにおける $n^2$ の総和は $10^8$ 以下であることが保証される。

出力

各テストケースについて、すべてのターンを通してバトルフレンドに与えることができる合計ダメージの最大値を表す整数を 1 行に出力せよ。

入出力例

入力例 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