#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+1;
int n;
int a[N];
int c[N];
bitset<4000000>b;
void solve(){
	cin >> n;
	b.reset();
	b[0]=1;
	int mx=0,s=0;
	for(int i=0; i<=2000 ;i++){
		c[i]=0;
	}
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		s+=a[i];
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=1; i<=n ;i++){
		for(int j=0; j<=a[i] ;j++){
			if(j%2!=s%2 || c[j]) continue;
			int v=(s+j)/2;
			if(v-a[i]>=0 && b[v-a[i]]){
				c[j]=true;
				ans++;
			}
		}
		b|=b<<a[i];
	}
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--){solve();/*cout << endl;*/}
}