Untitled

#include <iostream>
using namespace std;
int a[20001], n, sum;

int backtrack(int s, int e, int to) {
	//cout << s << ", " << e << ", " << to << endl;
	int st = 0, cur = 0;
	bool b = false;
	if (e - s > 1) {
		for (int i = s; i <= e; i++) {
			st += a[i];
			if (st == to - st) {
				b = true;
				cur = i;
				break;
			}
		}
	}
	else {
		if (a[s] == a[e] && e - s > 0) {
			b = true;
			cur = s;
		}
	}
	if (b) {
		if (cur - s > 0 && e - cur > 1) {
			int left = backtrack(s, cur, st);
			int right = backtrack(cur + 1, e, to - st);
			if (left > right)	return left + 1;
			else return right + 1;
		}
		else if (cur - s > 0 && e - cur == 1) {
			return backtrack(s, cur, st) + 1;
		}
		else if (cur - s == 0 && e - cur > 1) {
			return backtrack(cur + 1, e, to - st) + 1;
		}
		else {
			return 1;
		}
	}
	else {
		return 0;
	}
}

void solve(int index) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	cout << backtrack(0, n - 1, sum);
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}