//分析题意，求m的最小个数，说明原来a[j]能被其他a[1],a[2]线性表示出来的都不要

//状态表示：f[i][j],只选前i个物品，体积为j，能否满足

//状态转移:f[i][j]|=f[i][j-v[i]]

//用了类似线性筛法的思想，将不满足条件的筛掉

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110,M=25010;
int v[N],f[M];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>v[i];

        sort(v+1,v+n+1);
        int res=0,m=v[n];
        memset(f,0,sizeof f);
        f[0]=1;

        for(int i=1;i<=n;i++)
        {
            if(f[v[i]])continue;
            res++;

            for(int j=v[i];j<=m;j++)
                f[j]|=f[j-v[i]];
        }
        cout<<res<<endl;
    }
    return 0;
}