Chia đồ chơi

Sắn có một dãy \(N\) món đồ chơi xếp trong tủ theo thứ tự mua, món thứ \(i\) có giá \(v_i\). Sau khi thua cược, Sắn phải chia đồ chơi cho Mì theo cách sau: Sắn chọn trước một số nguyên \(x \in \{1, 2, 3\}\), sau đó hai bạn lần lượt lấy đồ chơi từ đầu dãy: Sắn lấy \(x\) món đầu tiên, Mì lấy \(x\) món tiếp theo, rồi lại đến Sắn \(x\) món, ... cho đến khi hết đồ (nếu lượt cuối còn ít hơn \(x\) món thì người đó lấy hết số còn lại).

Sắn muốn phần của mình có tổng giá trị lớn nhất có thể. Hãy chọn \(x\) tối ưu và in ra tổng giá trị đó.

Input

• Dòng đầu chứa số bộ test \(T\).
• Mỗi bộ test gồm hai dòng: dòng thứ nhất là \(N\), dòng thứ hai gồm \(N\) số nguyên \(v_1, \dots, v_N\).

Output

Với mỗi bộ test in một dòng: tổng giá trị lớn nhất Sắn có thể nhận.

Constraints

• \(1 \le T \le 10\)
• \(1 \le N \le 10^5\)
• \(1 \le v_i \le 10^9\)

Sample Input

2
5
9 2 4 6 1
7
3 8 8 1 5 2 7

Sample Output

15
26

Explanation

Bộ test 1: với \(x = 3\) Sắn lấy \(9, 2, 4\) được \(15\) (Mì lấy \(6, 1\)); các giá trị \(x = 1, 2\) chỉ cho \(14\) và \(12\). Bộ test 2: với \(x = 3\) Sắn lấy \(3, 8, 8\) và \(7\), tổng \(26\).