Hai chuyến tàu kì lạ

Bối cảnh

Có hai chuyến tàu A và B cùng với N ga xếp theo thứ tự từ 1 đến N. Có một mảng P có độ dài N−1, trong đó (P_i) (1 ≤ i < N) biểu thị thời gian mà bất kỳ chuyến tàu nào cần để di chuyển từ ga i đến ga (i+1).

Yêu cầu

Ban đầu, cả hai chuyến tàu đều ở ga 1. Chuyến tàu A xuất phát từ ga 1 và dừng tại ga N. Để đảm bảo an toàn, chuyến tàu B không thể xuất phát từ ga i trừ khi chuyến tàu A đã đến ga (i+1) (1 ≤ i < N).

Tìm thời gian tối thiểu sau khi chuyến tàu B đến ga N, kể từ khi chuyến tàu A rời ga 1.

Input

Dòng đầu tiên của đầu vào chứa một số nguyên T, biểu thị số lượng test case. Mỗi test case bao gồm hai dòng:

• Dòng đầu tiên của mỗi test case chứa một số nguyên N, biểu thị số lượng ga.
• Dòng tiếp theo chứa N−1 số nguyên cách nhau bởi dấu cách, P1, P2, ..., P(N−1).

Output

Với mỗi test case, xuất trên một dòng mới thời gian tối thiểu sau khi chuyến tàu B đến ga N.

Ràng buộc

• 1 ≤ T ≤ 100
• 2 ≤ N ≤ 10^5
• 1 ≤ P_i ≤ 10^3
• Tổng số N trên tất cả các test cases không vượt quá 10^5.

Ví dụ 1

Input

3
2
4
3
3 5
4
5 2 6

Output

13
8
19

Giải thích ví dụ

• Test case 1: Chuyến tàu A đến ga 2 tại thời điểm t = 4, và tại thời điểm này chuyến tàu B xuất phát từ ga 1 và đến ga 2 tại t = 4 + 4 = 8.

• Test case 2: Dưới đây là thời gian của hai chuyến tàu:

  • Tại t = 3, A đến ga 2 và B xuất phát từ ga 1.
  • Tại t = 6, B đến ga 2 nhưng A chưa đến ga 3, nên tàu B phải chờ tại ga 2.
  • Tại t = 8, A đến ga 3 và B xuất phát từ ga 2.
  • Tại t = 8 + 5 = 13, tàu B đến ga 3.

Thông tin học tập

• Buổi: B04
• Concepts: loops, two-process simulation, maximum tracking, conditionals
• Giới hạn kiến thức: B01-B04
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 25