Untitled

#include <iostream>
using namespace std;

long long T, n, a[100000], sum, cnt, maxCnt;
long long left, right;

int findMid(int left, int right, long long halfSum) {
	long long tmpsum = 0;
	for(int i=left; i<=right; i++) {
		tmpsum+=a[i];
		if(sum == halfSum)
			return i;
		else if( tmpsum >halfSum)
			return -1;
	}
	
}

void backtrack(int left, int right, long long sumCur, int cnt) {
	if(left == right || (sumCur%2 == 1)) {
		if(cnt > maxCnt) {
			maxCnt = cnt;
		}
		return;
	}
	int mid = findMid(left, right, sumCur/2) ;
	if(mid == -1) {
		if(cnt > maxCnt) {
			maxCnt = cnt;
		}
		return;
	}
	backtrack(left, mid, sumCur/2, cnt+1);
	backtrack(mid + 1, right, sumCur/2, cnt+1);
}

int main() {
	freopen("input.txt", "r", stdin);
	cin>>T;
	for(int tc=1; tc<=T; tc++) {
		sum = 0;
		cin>>n;
		for(int i=0; i<n; i++) {
			cin>>a[i];
			sum += a[i];
		}
		maxCnt = -1;
		cnt = 0;
		backtrack(0, n-1, sum, 0);
		cout<<cnt<<endl;

	}
	return 0; 
}