#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
int n;
const int maxN = 2002;
const int maxA = 2002;
typedef bitset<maxN * maxA> bs;
int A[maxN];
bool ok[maxN];
void solve() {
	cin >> n;
	int mx = 0;
	int S = 0;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		mx = max(mx, A[i]);
		S += A[i];
	}
	sort(A + 1, A + n + 1);
	for (int i = 0; i <= mx; i++) {
		ok[i] = false;
	}
	bs cur;
	cur[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int z = S % 2; z <= A[i]; z += 2) {
			if ((z + S) / 2 - A[i] >= 0 && cur[(z + S) / 2 - A[i]]) {
				ok[z] = true;
			}
		}
		cur |= (cur << A[i]);
	}
	int ans = 0;
	for (int i = 0; i <= mx; i++) {
		if (ok[i]) {
			// cout << i <<  " ";
			ans++;
		}
	}
	cout << ans << '\n';
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "r", stdin);
	int tst;
	cin >> tst;
	while (tst--) {
		solve();
	}
	return 0;
}