Bạn được cho một dãy số nguyên có độ dài $n$: $a_1, a_2, \dots, a_n$. Bạn có thể thực hiện thao tác sau đúng một lần:

• Chọn một hoán vị $p_1, p_2, \dots, p_n$ của $1, 2, \dots, n$.
• Sau đó, với $i$ từ $1$ đến $n$ theo thứ tự tự nhiên, thực hiện: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ trong đó $a_0 = 0$ và $a_{n+1} = 0$.

Mục tiêu của bạn là cực đại hóa tổng của tất cả các phần tử trong dãy sau khi thao tác hoàn tất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$).

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên biểu thị tổng lớn nhất có thể của tất cả các phần tử trong dãy sau khi thực hiện thao tác.

Ví dụ

Dữ liệu vào

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

Kết quả

22
85
72
79