Ti viene data una sequenza di interi di lunghezza $n$: $a_1, a_2, \dots, a_n$. Puoi eseguire la seguente operazione esattamente una volta:

• Scegliere una permutazione $p_1, p_2, \dots, p_n$ di $1, 2, \dots, n$.
• Poi, per $i$ da $1$ a $n$ nell'ordine naturale, eseguire: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ dove $a_0 = 0$ e $a_{n+1} = 0$.

Il tuo obiettivo è massimizzare la somma di tutti gli elementi nella sequenza dopo che l'operazione è stata completata.

Input

La prima riga contiene un singolo intero $t$ ($1 \le t \le 10^4$), il numero di casi di test. Per ciascun caso di test:

La prima riga contiene un intero $n$ ($1 \le n \le 2 \cdot 10^5$).

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

La somma di $n$ non supera $2 \cdot 10^5$.

Output

Per ciascun caso di test, stampa una singola riga con un intero che rappresenta la massima somma possibile di tutti gli elementi nella sequenza dopo aver eseguito l'operazione.

Esempio

Input

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

Output

22
85
72
79