Dany jest ciąg liczb całkowitych o długości $n$: $a_1, a_2, \dots, a_n$. Możesz wykonać następującą operację dokładnie jeden raz:

• Wybierz permutację $p_1, p_2, \dots, p_n$ liczb $1, 2, \dots, n$.
• Następnie dla $i$ od $1$ do $n$ w naturalnej kolejności wykonaj: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ gdzie $a_0 = 0$ oraz $a_{n+1} = 0$.

Twoim celem jest zmaksymalizowanie sumy wszystkich elementów w ciągu po zakończeniu operacji.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \cdot 10^5$).

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Suma $n$ nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz z liczbą całkowitą oznaczającą maksymalną możliwą sumę wszystkich elementów w ciągu po wykonaniu operacji.

Przykład

Wejście

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

Wyjście

22
85
72
79