Cuộc thi OLYMPIC TIN HỌC 2018 là cuộc thi dành cho những học sinh giỏi của các trường chuyên trên toàn quốc. BTC cuộc thi đã chuẩn bị rất kĩ lưỡng và mới đây họ vừa tiết lộ thông tin rằng ngoài việc thi những môn thi ra, mỗi trường sẽ phải cử một học sinh để tham gia một trò chơi đặc biệt. Cụ thể trò chơi đó được biết như sau:

• Đây là trò chơi đối kháng 1 với 1.
• Sẽ có ~N~ quân cờ "BIG DOMINOES" được xếp trên một hàng từ trái qua phải. Sở dĩ gọi là cờ "BIG DOMINOES" vì các số trên quân cờ này là rất lớn so với cờ DOMINOES thông thường.
• Với mỗi lượt chơi, mỗi thí sinh sẽ phải bốc lần lượt từ trái sang phải 1, 2 hoặc 3 quân "BIG DOMINOES" và số điểm thí sinh đó sẽ được cộng thêm một lượng là tổng giá trị của các số được viết trên quân cờ bốc ra. Hai thí sinh thay phiên bốc cho đến khi hết ~N~ quân cờ.

Vì rất giỏi về tư duy thuật toán nên Hải được chọn để đại diện cho trường LTT tham gia trò chơi này. Để luyện tập chuẩn bị cho trò chơi, Hải đã phải nhờ bạn tạo ra một con BOT cực kì thông minh để cùng Hải luyện tập.

Yêu cầu: Hãy tạo ra một con BOT để chơi trò chơi trên sao cho con BOT luôn mang về số điểm là lớn nhất có thể. Biết rằng, con BOT của bạn sẽ giành quyền chơi trước và Hải luôn chơi theo cách tối ưu nhất.

Input

• Dòng đầu tiên chứa một số nguyên dương ~T~ là số bộ dữ liệu (~1 \le T \le 5~).
• Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên dương ~N~ là số quân cờ "BIG DOMINOES" (~1 \le N \le 10^5~).
• Dòng thứ hai của mỗi bộ dữ liệu chứa ~N~ số nguyên dương ~A_i~ là giá trị của các số được ghi trên quân cờ thứ ~i~ (~0 \le A_i \le 10^9~).

Output

• Với mỗi bộ dữ liệu ghi ra trên một dòng số điểm lớn nhất có thể tương ứng với bộ dữ liệu đó.

Sample Input 1

2
5
333 2 2 2 0
5
0 2 2 2 333

Sample Output 1

337
333