Những chiếc rương bị yểm

Trên con đường đến ngôi làng của một nàng công chúa có \(N\) chiếc rương vàng nằm nối tiếp nhau theo thứ tự đi qua. Rương thứ \(i\) chứa \(x_i\) đồng vàng. Tuy nhiên, những chiếc rương này bị yểm bùa: nếu bạn đã lấy vàng ở rương \(i-1\) thì rương \(i\) sẽ không mở ra được nữa. Nói cách khác, không được lấy hai rương liên tiếp.

Hãy tính tổng số đồng vàng lớn nhất có thể mang đi.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên \(N\) là số rương; dòng tiếp theo chứa \(N\) số nguyên \(x_1, x_2, \dots, x_N\) (nếu \(N = 0\) thì dòng này để trống).

Output

Với mỗi bộ test, in ra một dòng là số vàng lớn nhất thu được.

Constraints

• \(1 \le t \le 10\)
• \(0 \le N \le 10^4\)
• \(0 \le x_i \le 10^4\)

Sample Input

3
6
4 1 1 9 1 3
0

4
5 5 5 5

Sample Output

16
0
10

Explanation

Bộ test đầu: lấy các rương 4, 9, 3 (vị trí 1, 4, 6) được \(16\). Bộ test thứ hai không có rương nào. Bộ test thứ ba: lấy hai rương cách nhau, được \(10\).