#include<bits/stdc++.h>
using namespace std;
long long a[105];
bool f[25005];
bool dfs(long long sum,long long id)
{
	if(sum<0)return 0;
	if(f[sum]==1)return 1;
	if(sum==0)return 1;
	for(long long i=0;i<id;i++)
	{
		if(a[i]==0)continue;
		if(dfs(sum-a[i],id))
		{
			f[a[id]]=1;
			f[sum-a[i]]=1;
			return 1;
		}
	}
	return 0;
}
int main()
{
	long long t;
	cin>>t;
	while(t--)
	{
		long long n,ans;
		cin>>n;
		memset(f,0,sizeof(f));
		ans=n;
		for(long long i=0;i<n;i++)
		{
			cin>>a[i];
		}
		sort(a,a+n);
		for(long long i=1;i<n;i++)
		{
			if(dfs(a[i],i))
			{
				a[i]=0;
				ans--;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}