Untitled

#include <iostream>
#define MAX 20001

using namespace std;

int N;
int arr[MAX];
long long prefixSum[MAX];
int ans;


//int findMid(int left, int right)
//{
//	long long sum;
//	int mid;
//	sum =  prefixSum[right] - prefixSum[left - 1];
//	long long half = sum/2;
//	long long key = prefixSum[left] + half;
//	while(left <= right){
//		mid  = (left + right) / 2;
//		if(key == prefixSum[mid])
//			return mid;
//		if(key < prefixSum[mid])
//			right = mid -1;
//		else
//			left = mid + 1;
//	}
//	return -1;
//}

int findMid(int left, int right, long long sum)
{
	long long half = sum / 2;
	long long tmpSum = 0;
	int mid;
	for(mid = left; tmpSum < sum /2 ; ++mid){
		tmpSum += arr[mid];
	}
	--mid;
	if(tmpSum == half) 
		return mid;
	else
		return -1;
}

void backTrack (int left, int right, long long sum, int cnt)
{
	if(left == right || sum % 2 == 1){
		if(cnt > ans)
			ans = cnt;
		return;
	}

	int mid = findMid(left, right, sum);
	if(mid == -1){
		if(cnt > ans)
			ans = cnt;
		return;
	}
	backTrack(left, mid, sum/2, cnt + 1);
	backTrack(mid + 1, right, sum/2, cnt + 1);
}

int main()
{
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N;
		long long sum = 0;
		for(int i = 0; i <N; i++){
			cin >> arr[i];
			sum += arr[i];
		}
		
		ans = 0;
		if(sum == 0)
			ans = N -1;
		else
			backTrack(0, N-1, sum, 0);

		cout << ans << endl;
		
	}
	return 0;
}

//input

20
42
0 2 0 2 0 0 0 0 2 0 0 2 2 0 2 2 2 2 0 0 0 2 0 0 2 2 2 2 2 2 0 0 0 0 2 0 2 0 2 0 2 2
24
2 0 0 2 2 0 0 0 0 2 0 2 0 2 0 2 0 0 0 2 0 0 2 0
64
999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994
70
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
103
4096 4096 1024 256 256 128 128 128 128 512 512 512 512 256 256 512 512 128 32 32 32 32 128 128 1024 1024 2048 512 512 1024 2048 2048 1024 512 512 2048 2048 2048 16384 16384 2048 256 128 128 512 256 256 512 2048 1024 1024 512 512 1024 1024 1024 2048 512 512 1024 4096 4096 4096 2048 2048 4096 2048 2048 2048 1024 512 256 16 16 32 64 128 2048 512 512 512 512 8192 8192 32768 32768 65536 16384 8192 4096 4096 16384 16384 32768 8192 8192 16384 65536 16384 16384 16384 8192 8192
77
2097152 1048576 1048576 2097152 1048576 262144 262144 524288 1048576 1048576 1048576 1048576 2097152 2097152 1048576 524288 524288 2097152 524288 524288 524288 524288 2097152 524288 262144 262144 524288 131072 131072 131072 131072 262144 65536 65536 32768 32768 65536 262144 262144 1048576 1048576 1048576 262144 262144 524288 524288 131072 65536 65536 32768 32768 65536 32768 32768 65536 2097152 2097152 131072 65536 65536 131072 131072 262144 65536 65536 131072 1048576 2097152 2097152 2097152 4194304 2097152 524288 524288 1048576 4194304 8388608
8
16384 8192 8192 16384 8192 8192 32768 32768
11
8760958 8760957 547560 547560 547560 273780 273780 2190239 4380479 4380479 4380478
15
21211 21211 21211 21211 21211 21211 21211 21211 21211 21211 21211 21211 21211 21211 21211
55
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0