Du får gitt en heltallsfølge med lengde $n$: $a_1, a_2, \dots, a_n$. Du kan utføre følgende operasjon nøyaktig én gang:

• Velg en permutasjon $p_1, p_2, \dots, p_n$ av $1, 2, \dots, n$.
• Deretter, for $i$ fra $1$ til $n$ i naturlig rekkefølge, utfør: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ der $a_0 = 0$ og $a_{n+1} = 0$.

Målet ditt er å maksimere summen av alle elementene i følgen etter at operasjonen er fullført.

Inndata

Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 10^4$), antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \cdot 10^5$).

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Summen av $n$ overstiger ikke $2 \cdot 10^5$.

Utdata

For hvert testtilfelle, skriv ut en enkelt linje med et heltall som representerer den maksimalt mulige summen av alle elementene i følgen etter å ha utført operasjonen.

Eksempel

Inndata

4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3

Utdata

22
85
72
79