Bạn được giao nhiệm vụ như sau: Cho một dãy số \(A\) bao gồm \(N\) số nguyên, yêu cầu hãy
chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các
số ở phần bên phải. Với mỗi lần như vậy bạn sẽ được 1 điểm, còn nếu không thể chia được
thì nhiệm vụ sẽ kết thúc. Sau khi chia thành công, bạn sẽ tiếp tục được chọn dãy số bên trái
hoặc bên phải để tiếp tục nhiệm vụ với các bước như trên cho đến khi kết thúc. Hãy tính
xem số điểm lớn nhất bạn có thể đạt được là bao nhiêu?

Input

Đọc từ file văn bản CHIADAY.INP:

• Dòng đầu tiên ghi một số nguyên \(T (1 \le T \le 10)\) là số lượng bộ dữ liệu. Mỗi
  bộ liệu bao gồm hai dòng:
• Dòng đầu tiên ghi một số nguyên \(N\) là số lượng phần tử của dãy \(A\).
• Dòng thứ hai gồm Nphần tử của dãy \(A\) được ghi cách nhau bởi dấu cách \((0 \le a_i \le 10^9)\).

Output

Ghi ra file văn bản CHIADAY.OUT

• Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 200\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \le 2000\).
• Subtask \(3\) (\(10\%\) số điểm): \(N \le 20000\).

Example

3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

0
2
3