Маленька Блакитна Рибка грає в 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