Mała Cyjanowa Rybka gra w Slay the Spire II i wybrała postać „Milcząca” (Silent).

Mała Cyjanowa Rybka musi teraz stoczyć walkę z „Przyjacielem Bojowym” (Battle Friend). Początkowo zarówno liczba ładunków „Trucizny” (Poison) Przyjaciela Bojowego, jak i twój poziom „Akcelerantu” (Accelerant) wynoszą $0$. W każdej z kolejnych $n$ tur następują po kolei poniższe zdarzenia:

1. Użycie „Zabójczej Trucizny” (Deadly Poison): zwiększ liczbę ładunków Trucizny Przyjaciela Bojowego o $x_i$.

2. Wybór, czy użyć „Akcelerantu”: wybierz, czy zwiększyć swój poziom Akcelerantu o $1$.

3. Aktywacja efektu Trucizny: niech twój poziom Akcelerantu wynosi $t$; powtórz następujące zdarzenie $t$ razy:

   • Niech liczba ładunków Trucizny Przyjaciela Bojowego wynosi $x$. Jeśli $x > 0$, zadaj Przyjacielowi Bojowemu $x$ punktów obrażeń i zmniejsz liczbę ładunków Trucizny o $1$; w przeciwnym razie, gdy $x = 0$, nic się nie dzieje.

Zauważ, że zarówno ładunki Trucizny, jak i poziom Akcelerantu przechodzą między turami i nie znikają.

Mała Cyjanowa Rybka chce zmaksymalizować łączne obrażenia zadane Przyjacielowi Bojowemu w ciągu tych $n$ tur. Wypisz tę maksymalną wartość obrażeń.

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 5000$).

Drugi wiersz zawiera $n$ liczb całkowitych $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), oznaczających liczbę ładunków Trucizny dodawanych Przyjacielowi Bojowemu w każdej turze.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$, a suma $n^2$ po wszystkich przypadkach testowych nie przekracza $10^8$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą oznaczającą maksymalne łączne obrażenia, jakie można zadać Przyjacielowi Bojowemu we wszystkich turach.

Przykład

Wejście 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

Wyjście 1

33
11
750
725