You are given an array ~a~ consisting of ~n~ positive integers and a variable ~S~. Initially, ~S=0~.

You are allowed to perform the following operation any number of times (possibly zero): choose three elements with indices ~i, i+1, i+2~ (~1\le i\le n-2~) such that ~\min(a_i,a_{i+1},a_{i+2})\ne -1~, then update as follows:

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

• ~a_i:=-1~

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

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

Your task is to determine a way to perform the operations so that after all operations, ~S~ is as large as possible.

Input

The first line contains an integer ~t~ (~1 \le t \le 10^3~) — the number of test cases. The description of each test case is as follows:

• The first line contains a positive integer ~n~ (~1 \le n \le 5000~) — the length of the array ~a~.

• The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) — the values of the elements of the array.

It is guaranteed that the sum of ~n~ over all test cases does not exceed ~5000~.

Output

For each test case, print a single integer on a line — the maximum possible value of ~S~.

Scoring

The total score for this problem is ~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

In the first test case, no operation can be performed, so ~S=0~.

In the second test case, the only way to perform one operation is to apply it to the whole array; then ~S=1+2+3=6~, which is also the maximum possible value.

In the third test case, there are two ways to perform one operation: on elements ~a_1,a_2,a_3~ (~S=6+7+3=16~) or on ~a_2,a_3,a_4~ (~S=7+3+6=16~). Both ways give ~S=16~, and this is the maximum possible value.

In the fourth test case, one of the optimal ways is:

• Choose the three elements ~a_2,a_3,a_4~, after which ~S=81~.

• Choose the three elements ~a_5,a_6,a_7~, after which ~S=161~.

It can be proved that no other way yields a better result.