On vous donne une suite d'entiers de longueur $n$ : $a_1, a_2, \dots, a_n$. Vous pouvez effectuer l'opération suivante exactement une fois :

• Choisir une permutation $p_1, p_2, \dots, p_n$ de $1, 2, \dots, n$.
• Ensuite, pour $i$ allant de $1$ à $n$ dans l'ordre naturel, exécuter : $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ où $a_0 = 0$ et $a_{n+1} = 0$.

Votre objectif est de maximiser la somme de tous les éléments de la suite une fois l'opération terminée.

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 10^4$), le nombre de cas de test. Pour chaque cas de test :

La première ligne contient un entier $n$ ($1 \le n \le 2 \cdot 10^5$).

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

La somme de $n$ ne dépasse pas $2 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier représentant la somme maximale possible de tous les éléments de la suite après avoir effectué l'opération.

Exemple

Entrée

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

Sortie

22
85
72
79