Anda diberikan sebuah barisan bilangan bulat dengan panjang $n$: $a_1, a_2, \dots, a_n$. Anda dapat melakukan operasi berikut tepat satu kali:

• Pilih sebuah permutasi $p_1, p_2, \dots, p_n$ dari $1, 2, \dots, n$.
• Kemudian, untuk $i$ dari $1$ hingga $n$ dalam urutan alami, jalankan: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ dengan $a_0 = 0$ dan $a_{n+1} = 0$.

Tujuan Anda adalah memaksimalkan jumlah semua elemen dalam barisan setelah operasi selesai.

Masukan

Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 10^4$), banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \cdot 10^5$).

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Jumlah dari $n$ tidak melebihi $2 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan jumlah maksimum yang mungkin dari semua elemen dalam barisan setelah melakukan operasi tersebut.

Contoh

Masukan

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

Keluaran

22
85
72
79