Untitled

package Array_Game;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, res;
	static long sum;
	static int[] a = new int[20005];
	
	public static int index(int l, int r, long sum){
		if(l >= r) return -1;
		if(sum%2 == 1) return -1;
		long s = 0;
		for(int i = l; i < r; i++){
			s += a[i];
			if(s == sum/2){
				return i;
			}
			if(s > sum/2){
				return -1;
			}
		}
		return -1;
	}
	public static void backTrack(int l, int r, int count, long sum) {
//		System.out.println(l + " " + r + " " + " " + count);

//		if (sum % 2 == 1) {
//			res = Math.max(res, count);
//			return;
//		}
//		if(r - l == 1){
//			
//			return;
//		}
		int x = index(l, r, sum);
		if(x == -1){
			res = Math.max(res, count);
			return;
		}
		backTrack(l, x+1, count+1, sum/2);
		backTrack(x+1, r, count+1, sum/2);
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			a = new int[n];
			sum = 0;
			for (int i = 0; i < n; i++) {
				a[i] = scanner.nextInt();
				
				sum += a[i];
			}
			
			res = 0;
			if(sum == 0){
				res = n-1;
			}else{
				backTrack(0, n, 0, sum);
			}
			
			
			
			
			System.out.println(res);
		}
		scanner.close();
	}
}