Cho một dãy số ~A~ bao gồm ~N~ số nguyên dương, 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 bước như vậy người chơi được ~1~ điểm còn nếu không thể chia được thì trò chơi sẽ kết thúc. Sau khi chia thành công người chơi sẽ được chọn dãy số bên trái hoặc bên phải để tiếp tục cuộc chơi với các bước như trên cho đến khi trò chơi kết thúc.

Yêu cầu: An muốn kiếm được số điểm cao nhất có thể. Bạn hãy tính xem số điểm lớn nhất mà An có thể đạt được là bao nhiêu?

Dữ liệu

• 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ộ dữ liệu bao gồm hai dòng:
  • Dòng 1 ghi một số nguyên ~N~ là số lượng phần tử của dãy ~A~.
  • Dòng 2 gồm ~N~ phầ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~).

Kết quả

Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là số điểm đạt được.

Ví dụ

DAYSO.INP

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

DAYSO.OUT

0
2
3

Giới hạn

• Có 60% test của bài có ~N \le 2^{11}~.
• Có 40% test của bài có ~2^{11} < N \le 2^{14}~.