#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int ans,n,a[105],T; 
bool f[25005];
int main(){
	cin>>T;
	while(T-->0){
		memset(f,0,sizeof(f));
		cin>>n;ans=n;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		f[0]=true;
		for(int i=1;i<=n;i++){
			if(f[a[i]]){
				ans--;
				continue;
			}
			for(int j=a[i];j<=a[n];j++)
				f[j]|=f[j-a[i]];
		}
		cout<<ans<<endl;	
	}
}