Lilla Cyanfisken spelar Slay the Spire II och har valt karaktären "Den Tysta" (Silent).

Lilla Cyanfisken måste nu strida mot en "Stridsvän" (Battle Friend). Från början är både Stridsvännens antal lager av "Gift" (Poison) och din nivå av "Accelerant" (Accelerant) lika med $0$. Under var och en av de följande $n$ rundorna inträffar följande händelser i tur och ordning:

1. Använd "Dödligt Gift" (Deadly Poison): öka Stridsvännens lager av Gift med $x_i$.

2. Välj om du vill använda "Accelerant": välj om du vill öka din Accelerant-nivå med $1$.

3. Utlös Gifteffekten: låt din Accelerant-nivå vara $t$, och upprepa följande händelse $t$ gånger:

   • Låt antalet lager av Gift på Stridsvännen vara $x$. Om $x > 0$, tillfoga Stridsvännen $x$ skada och minska antalet lager av Gift med $1$; annars, om $x = 0$, händer ingenting.

Observera att både lager av Gift och Accelerant-nivån sparas mellan rundorna och inte försvinner.

Lilla Cyanfisken vill maximera den totala skadan som tillfogas Stridsvännen under dessa $n$ rundor. Skriv ut denna maximala skada.

Indata

Indata innehåller flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($1 \le n \le 5000$).

Den andra raden innehåller $n$ heltal $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), som anger antalet lager av Gift som läggs till Stridsvännen under varje runda.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$, och att summan av $n^2$ över alla testfall inte överstiger $10^8$.

Utdata

För varje testfall, skriv ut en rad med ett heltal som anger den maximala totala skadan som kan tillfogas Stridsvännen under alla rundor.

Exempel

Indata 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