Pieni Syaanikala pelaa Slay the Spire II -peliä ja on valinnut hahmon ”Hiljainen” (Silent).

Pienen Syaanikalan täytyy nyt taistella ”Taisteluystävää” (Battle Friend) vastaan. Aluksi sekä Taisteluystävän ”Myrkky”-kerrosten (Poison) määrä että sinun ”Kiihdyttimen” (Accelerant) tasosi ovat $0$. Seuraavien $n$ vuoron aikana jokaisella vuorolla tapahtuvat järjestyksessä seuraavat tapahtumat:

1. Käytä ”Tappavaa myrkkyä” (Deadly Poison): kasvata Taisteluystävän Myrkky-kerrosten määrää $x_i$:llä.

2. Valitse, käytätkö ”Kiihdytintä”: valitse, kasvatatko Kiihdyttimesi tasoa $1$:llä.

3. Laukaise Myrkyn vaikutus: olkoon Kiihdyttimesi taso $t$, toista seuraava tapahtuma $t$ kertaa:

   • Olkoon Taisteluystävän Myrkky-kerrosten määrä $x$. Jos $x > 0$, tee Taisteluystävään $x$ pistettä vahinkoa ja vähennä Myrkky-kerrosten määrää $1$:llä; muuten, jos $x = 0$, mitään ei tapahdu.

Huomaa, että sekä Myrkky-kerrokset että Kiihdyttimen taso säilyvät vuorojen yli eivätkä katoa.

Pieni Syaanikala haluaa maksimoida Taisteluystävään näiden $n$ vuoron aikana tehdyn kokonaisvahingon. Tulosta tämä suurin mahdollinen vahinko.

Syöte

Syöte sisältää useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 5000$).

Toinen rivi sisältää $n$ kokonaislukua $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), jotka ilmoittavat Taisteluystävään kullakin vuorolla lisättävien Myrkky-kerrosten määrän.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$, ja lukujen $n^2$ summa yli kaikkien testitapausten on enintään $10^8$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: suurimman mahdollisen kokonaisvahingon, joka Taisteluystävään voidaan tehdä kaikkien vuorojen aikana.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

33
11
750
725