Du får en heltalsföljd av längd $n$: $a_1, a_2, \dots, a_n$. Du kan utföra följande operation exakt en gång:

• Välj en permutation $p_1, p_2, \dots, p_n$ av $1, 2, \dots, n$.
• Utför sedan, för $i$ från $1$ till $n$ i naturlig ordning: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ där $a_0 = 0$ och $a_{n+1} = 0$.

Ditt mål är att maximera summan av alla element i följden efter att operationen har slutförts.

Indata

Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 10^4$), antalet testfall. För varje testfall:

Den första raden innehåller ett heltal $n$ ($1 \le n \le 2 \cdot 10^5$).

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Summan av $n$ överstiger inte $2 \cdot 10^5$.

Utdata

För varje testfall, skriv ut en enda rad med ett heltal som representerar den maximalt möjliga summan av alla element i följden efter att operationen har utförts.

Exempel

Indata

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