Ngày xửa ngày xưa có một nàng công chúa dễ thương tên là Farida sống trong một lâu đài cùng với cha, mẹ và chú của mình. Trên đường đến lâu đài có nhiều quái vật. Mỗi người trong số họ có một số tiền vàng. Mặc dù chúng là quái vật nhưng chúng sẽ không làm bạn bị thương. Thay vào đó, chúng sẽ đưa cho bạn những đồng tiền vàng, nhưng quái vật \(i\) chỉ đưa vàng cho bạn khi và chỉ khi bạn không lấy bất kỳ đồng xu nào từ quái vật \(i-1\)

Để kết hôn với công chúa Farida, bạn phải vượt qua tất cả các quái vật và thu thập càng nhiều tiền càng tốt. Dựa vào số lượng đồng xu vàng mà mỗi quái vật có, hãy tính số lượng tiền tối đa bạn có thể thu thập trên đường đến lâu đài.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(t\) là số lượng test \((1 \le t \le 10)\)
• Mỗi trường hợp thử nghiệm bắt đầu bằng \(N\) - số lượng quái vật. \((1 \le N \le 10^4)\)
• Dòng tiếp theo sẽ có \(N\) số \(x_1,x_2,x_3...,x_n\) \((0 \le x_i \le 10^4)\) Với \(x_i\) là số đồng vàng quái vật thứ \(i\) có. Quái vật được mô tả theo thứ tự họ gặp trên đường đến lâu đài.

Dữ liệu ra

• In ra \(t\) dòng, mỗi dòng là một đáp án cho một trường hợp thử nghiệm.

Input 1

2
5
1 2 3 4 5
1
10

Output 1

9
10