Cho một dãy số ~A~ bao gồm ~N~ số nguyên dương. Hãy chia dãy thành 2 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: Hãy tính số điểm lớn nhất mà An có thể đạt được.

Input

• Dòng đầu tiên chứa 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:
• Dòng 1: chứa số nguyên ~n~ (~1 \le n \le 2^{14}~) số lượng phần tử của dãy ~A~.
• Dòng 2: gồm ~n~ số nguyên của dãy ~A~ được ghi cách nhau bởi dấu cách (~0 \le A_i \le 10^9~).

Output

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

Sample Input 1

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

Sample Output 1

0
2
3