Дана последовательность целых чисел длины $n$: $a_1, a_2, \dots, a_n$. Вы можете выполнить следующую операцию ровно один раз:

• Выбрать перестановку $p_1, p_2, \dots, p_n$ чисел $1, 2, \dots, 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