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. 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 vào

• 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: Ghi \(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)\).

Dữ liệu ra

• 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.

Input 1

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

Output 1

0  
2  
3

Giải thích

• Bộ \(1\): Không chia được nên điểm là \(0\).
• Bộ \(2\): Chia được thành hai phần \([3, 4]\) và \([2, 2]\), sau đó chia tiếp \([3, 4]\) thành \([3]\) và \([4]\), tổng cộng \(2\) điểm.
• Bộ \(3\): Chia được tối đa \(3\) lần.

Ràng buộc

• 60% test có \(N \le 2^{11}\)
• 40% test có \(2^{11} \le N \le 2^{14}\)