Lille Cyanfisk spiller Slay the Spire II og har valgt karakteren «Den Stille» (Silent).

Lille Cyanfisk må nå kjempe mot en «Kampvenn» (Battle Friend). Til å begynne med er både Kampvennens antall lag med «Gift» (Poison) og ditt nivå av «Akselerant» (Accelerant) lik $0$. I hver av de neste $n$ rundene skjer følgende hendelser i rekkefølge:

1. Bruk «Dødelig Gift» (Deadly Poison): øk Kampvennens lag med Gift med $x_i$.

2. Velg om du vil bruke «Akselerant»: velg om du vil øke Akselerant-nivået ditt med $1$.

3. Utløs Gifteffekten: la Akselerant-nivået ditt være $t$, og gjenta følgende hendelse $t$ ganger:

   • La antall lag med Gift på Kampvennen være $x$. Hvis $x > 0$, påfør Kampvennen $x$ skade og reduser antall lag med Gift med $1$; ellers, hvis $x = 0$, skjer ingenting.

Merk at både lag med Gift og Akselerant-nivået beholdes mellom rundene og ikke forsvinner.

Lille Cyanfisk ønsker å maksimere den totale skaden som påføres Kampvennen i løpet av disse $n$ rundene. Skriv ut denne maksimale skaden.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($1 \le n \le 5000$).

Den andre linjen inneholder $n$ heltall $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), som angir antall lag med Gift som legges til Kampvennen i hver runde.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^6$, og at summen av $n^2$ over alle testtilfeller ikke overstiger $10^8$.

Utdata

For hvert testtilfelle skal du skrive ut én linje med ett heltall som angir den maksimale totale skaden som kan påføres Kampvennen over alle rundene.

Eksempel

Inndata 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

Utdata 1

33
11
750
725