Luân rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Anh ta giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, Ngân sẽ không bao giờ lấy được đồ chơi của anh ta. Nhưng vì một lần không may mắn, Luân đã thua Ngân trong một vụ cá cược toán học. Và Ngân đã yêu cầu Luân chia sẻ đồ chơi. Bởi vì Luân không muốn mất nhiều tiền nên anh ta đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất. Chiến lược đó như sau:

• Đồ chơi được giữ theo thứ tự từ \(1 .. n\)
• Luân bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy \(x\) đồ chơi liên tiếp.
• Ngân sau đó sẽ chọn đúng \(x\) đồ chơi tiếp theo còn lại (chú ý là Ngân sẽ chọn số đồ chơi bằng với Luân, trừ khi số đồ chơi còn lại nhỏ hơn \(x\)).
• Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.

Bạn được cho một dãy của đồ chơi với giá của chúng. Hãy giúp Luân lấy được đồ chơi với số tiền lớn nhất có thể. Luân chỉ có thể chọn \(1, 2\) hay \(3\) đồ chơi (\(x\) có giá trị \(1, 2\) hay \(3\)).

Dữ liệu vào

• Dòng đầu tiên là \(T\), số lượng testcase. \((1 \le T \le 10)\)
• Mỗi testcase chứa \(N\) ở dòng đầu tiên \((1 \le N \le 10^5)\).
• Dòng thứ \(2\) là \(N\) số nguyên là giá tiền của các đồ chơi. \((1 \le v_i \le 10^9)\)

Dữ liệu ra

• In ra \(1\) số nguyên trên một dòng cho mỗi testcase là tổng số tiền lớn nhất của các đồ chơi mà Luân chọn.

Input 1

2
4
5 4 3 2
6
10 8 7 11 15 20

Output 1

12
53