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 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 thứ \(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 thứ \(i-1\).

Yêu cầu

• Lấy số lượng đồng xu nhiều nhất

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng bộ test \((1 \le T \le 10)\).
• Mỗi trường hợp thử nghiệm bắt đầu bằng \(N\) là số lượng quái vật \(0 \le N \le 10^4\)
• Dòng tiếp theo sẽ có \(N\) số \(x_1, x_2, ... x_n\) \((0 \le x_i \le 10^9)\). 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