Дано послідовність цілих чисел довжини $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