Cho một dãy số ~a~ gồm ~n~ số nguyên dương và một biến ~S~. Ban đầu, ~S=0~.

Bạn được phép thực hiện thao tác sau một số lần (có thể không thực hiện lần nào): Chọn ba phần tử có chỉ số lần lượt là ~i, i+1, i+2~ (~1\le i\le n-2~) sao cho ~\min(a_i,a_{i+1},a_{i+2})\ne -1~, sau đó cập nhật như sau:

• ~S:=S+a_i+a_{i+1}+a_{i+2}~

• ~a_i:=-1~

• ~a_{i+1}:=-1~

• ~a_{i+2}:=-1~

Nhiệm vụ của bạn là xác định phương án thực hiện thao tác sao cho sau khi thực hiện, ~S~ đạt giá trị lớn nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 10^3~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 5000~) — độ dài của dãy ~a~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) — giá trị của các phần tử trong dãy.

Đảm bảo rằng tổng ~n~ qua tất cả các test case không vượt quá ~5000~.

Output

Với mỗi test case, in ra duy nhất một số nguyên trên một dòng là giá trị lớn nhất có thể đạt được của ~S~.

Scoring

Tổng điểm cho bài này là ~500~.

Sample Input 1

4
2
3 6
3
1 2 3
4
6 7 3 6
8
6 7 67 7 6 7 67 6

Sample Output 1

0
6
16
161

Notes

Trong test case đầu tiên, ta không thể thực hiện bất kỳ thao tác nào, vì thế nên ~S=0~.

Trong test case thứ hai, cách duy nhất để thực hiện một thao tác là thực hiện trên toàn bộ dãy, khi đó ~S=1+2+3=6~, và đây cũng là giá trị lớn nhất có thể đạt được.

Trong test case thứ ba, có hai cách để thực hiện một thao tác là thực hiện trên các phần tử ~a_1,a_2,a_3~ (~S=6+7+3=16~) hoặc ~a_2,a_3,a_4~ (~S=7+3+6=16~). Cả hai cách đều cho giá trị ~S=16~, và đây là giá trị lớn nhất có thể đạt được.

Trong test case thứ tư, một trong những phương án tối ưu nhất là:

• Chọn ba phần tử ~a_2,a_3,a_4~, sau khi thực hiện thì ~S=81~.

• Chọn ba phần tử ~a_5,a_6,a_7~, sau khi thực hiện thì ~S=161~.

Có thể chứng minh rằng không có phương án nào khác cho kết quả tối ưu hơn.