给定一个长度为 $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$。

输出格式

对于每个测试用例，输出一行一个整数，表示执行操作后序列中所有元素可能的最大总和。

样例

输入格式 1

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

输出格式 1

22
85
72
79