Маленькая Голубая Рыбка играет в 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