/*
    如果能把1 ~ 9 都表示出来， 就能表示出N*
    如果能表示出1，就能表示所有的数
    在不能表示出1的集合A中，如果能表示出2 就能表示出所有2的倍数 和 A中第一个大于2的奇数后面的所有奇数
    在不能表示1,2的集合B中，如果能表示出3 就能表示出所有3的倍数（其他的分析比较复杂）
    对于一个最多有100种货币 货币的面值最大为25000的集合
    要构建一个和他等价的集合 并且使集合的长度最小 要怎么做？
    粗暴想法：  直接用1集合遍历所有数，每个数的表示法为0 or 不为0 
                再用2集合遍历一次， 看得到的序列是否一样
    问题1 所谓“所有的数”要遍历到多少？  先pass这一想法

    只要找到一个集合2，能表示所有集合1的数，说明所有集合1能表示的数集合2都能表示，
    反过来，这个集合2中所有的数都可以由集合1表示，说明集合2能表示的数集合1都能表示。
    则成立
    这个想法明显强于粗暴想法

    据此分析
    给定一个集合后 找到所有（？）能表示这一集合的数，然后用这个集合去从小到大表示， 如果存在不能表示的数则pass
    否则选择能表示的最小集合

    找到所有不现实
    因为集合1、2要互相表示，所以最小值一定要相等。
    因为集合2要表示集合1，且尽可能的小，所以肯定用不上比集合1中最大的数还大的数。
    所以只要找集合1min~集合1max中最小的等价集合
    这样可以从集合1出发，把集合1扩充成一个step为1的集合，
    然后用集合1去表示这个集合，去掉所有不能表示的数（表示方法为0的数）

    ！！！新思路 如果一个集合可以缩小，那么一定存在冗余的数 即可以被集合中其他数表示的数
    实质上只要找到这样的数并去掉 剩下的就是最小集合！！！！
    可以把每一个数组都sort后 从前往后 看是否有数能被前面的数表示 有则res--!!!

*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 25010;

int T, n;
int a[N], f[M];

int main()
{
    scanf("%d", &T);

    while (T -- )
    {
        memset(f, 0, sizeof f);
        scanf("%d", &n);

        int res = n;
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        sort(a + 1, a + n + 1);

        // for (int i = 1; i <= n; i ++ ) cout << a[i] << ' ';
        // puts("");

        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = a[i]; j <= a[n]; j ++ )
                f[j] += f[j - a[i]];

        // for (int i = 1; i <= n; i ++ )
        //     cout << f[a[i]] << ' ';
        // puts("");

        for (int i = 1; i <= n; i ++ )
            if (f[a[i]] != 1)
                res -- ;

        printf("%d\n", res);
    }

    return 0;
}