https://www.luogu.com.cn/record/159859264 之前30分的，关o2变85了

#include<bits/stdc++.h>
using namespace std;
int a[510];
bool book[50010];
int main(){
	int t,n,ans;
	cin>>t;
	while(t--){
		cin>>n;
		ans=n;
		memset(book,0,sizeof(book));
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		book[0]=1;
		for(int i=1;i<=n;i++){
			if(book[a[i]]==1){
				ans--;
				continue;
			}
			for(int j=1;j<=a[n];j++){
				if(book[j]==1) continue;
				if(book[j-a[i]]==1) book[j]=1;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}