長さ $n$ の整数列 $a_1, a_2, \dots, a_n$ が与えられます。以下の操作をちょうど 1 回行うことができます。

• $1, 2, \dots, n$ の順列 $p_1, p_2, \dots, p_n$ を 1 つ選ぶ。
• その後、$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$ とする。

あなたの目的は、操作が完了した後の数列のすべての要素の総和を最大化することです。

入力

1 行目には、テストケースの個数を表す 1 つの整数 $t$ ($1 \le t \le 10^4$) が与えられます。各テストケースについて：

1 行目には、整数 $n$ ($1 \le n \le 2 \cdot 10^5$) が与えられます。

2 行目には、$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

出力

22
85
72
79