Đêm Halloween sắp đến, Quốc Vương Vịt quyết định tổ chức Kỳ thi Nông Dân Tài Ba để chọn ra người trồng bí ngô giỏi nhất vương quốc. Vịt Vàng, chú vịt vui tính nhất vùng đầm sen, hăng hái ghi danh tham dự.

Đề thi như sau. Vịt Vàng được giao một luống đất dài, trên đó chú trồng n gốc bí ngô thành một hàng, đánh số từ 1 đến n theo thứ tự từ trái sang phải. Quả bí ngô thứ i có điểm ma thuật là ~a_i~. Bí ngô cười tươi có ~a_i~ dương, mang lại may mắn và niềm vui. Nhưng cũng có những quả bí ngô bị nguyền, có ~a_i~ âm, vì chúng mang lại xui xẻo và tai ương cho mọi người.

Để thử tài các thí sinh, Quốc Vương ban cho mỗi người một cây gậy phép và một chiếc giỏ thu hoạch. Vịt Vàng phải thực hiện hai bước, theo đúng thứ tự:

• Bước 1 (Phép đảo ngược): Chọn hai vị trí l, r (~1 \le l \le r \le n~). Vịt Vàng vung gậy phép để đảo ngược thứ tự các quả bí ngô trong đoạn từ vị trí l đến vị trí r.
• Bước 2 (Thu hoạch): Chọn một số nguyên k (~0 \le k \le n~). Vịt Vàng chỉ hái k quả bí ngô đầu tiên tính từ bên trái (sau khi đã đảo) bỏ vào giỏ. Những quả còn lại bị bỏ lại trên luống.

Điểm số của Vịt Vàng bằng tổng điểm ma thuật của các quả bí ngô trong giỏ. Nếu Vịt Vàng chọn k = 0, giỏ trống và điểm số bằng 0.

Hãy giúp Vịt Vàng chọn l, r, k sao cho điểm số đạt được là lớn nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (~1 \le t \le 10^4~) — số lượng bộ test.

Với mỗi bộ test:

• Dòng đầu tiên chứa số nguyên n (~2 \le n \le 2 \cdot 10^5~).
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Tổng n trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất — điểm số lớn nhất mà Vịt Vàng có thể đạt được.

Ví dụ

Input

4
6
4 -5 3 -2 6 -8
3
-3 -1 -2
7
2 -1 -4 7 -3 8 -6
2
-4 10

Output

11
0
14
10

Giải thích

• Test 1: Vịt Vàng đảo đoạn ~[2, 5]~, luống bí ngô thành ~4, 6, -2, 3, -5, -8~. Chú hái ~k = 4~ quả đầu tiên, được ~4 + 6 - 2 + 3 = 11~.
• Test 2: Toàn bộ bí ngô đều bị nguyền, nên tốt nhất là không hái quả nào ~(k = 0)~, điểm số bằng 0.
• Test 3: Vịt Vàng đảo đoạn ~[2, 6]~, luống bí ngô thành ~2, 8, -3, 7, -4, -1, -6~. Chú hái ~k = 4~ quả đầu tiên, được ~2 + 8 - 3 + 7 = 14~.
• Test 4: Vịt Vàng đảo đoạn ~[1, 2]~, luống bí ngô thành ~10, -4~. Chú hái ~k = 1~ quả đầu tiên, được ~10~.