Gegeben ist eine Folge ganzer Zahlen der Länge $n$: $a_1, a_2, \dots, a_n$. Du kannst die folgende Operation genau einmal ausführen:

• Wähle eine Permutation $p_1, p_2, \dots, p_n$ von $1, 2, \dots, n$.
• Führe dann für $i$ von $1$ bis $n$ in der natürlichen Reihenfolge Folgendes aus: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ wobei $a_0 = 0$ und $a_{n+1} = 0$ gilt.

Dein Ziel ist es, die Summe aller Elemente in der Folge nach Abschluss der Operation zu maximieren.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 10^4$), die Anzahl der Testfälle. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \cdot 10^5$).

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Die Summe von $n$ überschreitet nicht $2 \cdot 10^5$.

Ausgabe

Gib für jeden Testfall eine einzige Zeile mit einer ganzen Zahl aus, die die maximal mögliche Summe aller Elemente in der Folge nach dem Ausführen der Operation darstellt.

Beispiel

Eingabe

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

Ausgabe

22
85
72
79