給定一個長度為 $n$ 的整數序列：$a_1, a_2, \dots, a_n$。你可以執行以下操作恰好一次：

• 選擇 $1, 2, \dots, n$ 的一個排列 $p_1, p_2, \dots, p_n$。
• 然後，對於 $i$ 從 $1$ 到 $n$ 按自然順序執行： $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ 其中 $a_0 = 0$ 且 $a_{n+1} = 0$。

你的目標是最大化操作完成後序列中所有元素的總和。

輸入格式

第一行包含一個整數 $t$ ($1 \le t \le 10^4$)，表示測試資料的組數。對於每組測試資料：

第一行包含一個整數 $n$ ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$)。

所有測試資料中 $n$ 的總和不超过 $2 \cdot 10^5$。

輸出格式

對於每組測試資料，輸出一行一個整數，表示執行操作後序列中所有元素可能的最大總和。

範例

輸入

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

輸出

22
85
72
79