畀定一個長度為 $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