You are given an integer sequence of length $n$: $a_1, a_2, \dots, a_n$. You can perform the following operation exactly once:

• Choose a permutation $p_1, p_2, \dots, p_n$ of $1, 2, \dots, n$.
• Then, for $i$ from $1$ to $n$ in the natural order, execute: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ where $a_0 = 0$ and $a_{n+1} = 0$.

Your goal is to maximize the sum of all elements in the sequence after the operation is completed.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$), the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

The sum of $n$ does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single line with an integer representing the maximum possible sum of all elements in the sequence after performing the operation.

Example

Input

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

Output

22
85
72
79