#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<bitset>

 using namespace std;

 typedef long long ll;

 const int maxn=,maxa=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){

         if(c=='-') neg=-;

         c=getchar();

     }

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 int a[maxn],N;

 bool f[];

 int main(){

     // freopen("money.in","r",stdin);

     // freopen("money.out","w",stdout);

     int i,j,k;

     for(int T=rd();T;T--){

         N=rd();

         int ans=N;

         for(i=;i<=N;i++) a[i]=rd();

         memset(f,,sizeof(f));

         sort(a+,a+N+);

         int M=a[N];

         f[]=;

         for(i=;i<=N;i++){

             if(f[a[i]]) ans--;

             else{

                 for(j=a[i];j<=M;j++){

                     f[j]|=f[j-a[i]];

                 }

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }