#include<cstdio>
#include<set>
#include<algorithm>
//#include<ext/hash_set>
using namespace std;
//using namespace __gnu_cxx;
int sum[1<<15];
//hash_set<int> se;
set<int> se[50001];
void check(int a,int b,int c){
	if(a>b)swap(a,b);
	if(b>c)swap(b,c);
	if(a>b)swap(a,b);
	if(a+b<=c)return;
	se[a].insert(b-a);
}
int main(){
	int Tc;
	for(scanf("%d",&Tc);Tc--;/*printf("%d\n",se.size())*/){
		int a[16],n,s;
		scanf("%d",&n);
		for(int i=s=0;i<n;++i){
			scanf("%d",a+i);
			s += a[i];
		}
		sum[0]=0;
		for(int z=1,msk=(1<<n) -1;z<=msk;++z)
			sum[z] = sum[z-(z&-z)] + a[__builtin_ctz(z&-z)];
		for(int z=1,msk=(1<<n) -1;z<=msk;++z){
			if(sum[z]*3>s)continue;
			for(int bm=msk^z,b=bm;b;b=(b-1)&bm)
			if(sum[b]>=sum[z]){
				check(sum[z],sum[b],s-(sum[z]+sum[b]));
			}
		}
		int ans =0;
		for(int i=1;i<=50000;++i)
		if(se[i].size()){
			ans+=se[i].size();
			se[i].clear();
		}
		printf("%d\n",ans);
	}
}