!

using namespace std;
typedef long long ll;
const int inf = 5000005;
int f[25005];
int a[105];
int i, j, n, T, ans;
int main() {
ios::sync_with_stdio(false);

cin >> T;
while (T--) {
    memset(f, 0, sizeof(f));
    cin >> n;
    ans = n;
    for (i = 1; i <= n; i++) { cin >> a[i]; }
    sort(a + 1, a + n + 1);
    f[0] = 1;
    for (i = 1; i <= n; i++) {
        if (f[a[i]]) {
            ans--;
            continue;
        }
        for (j = a[i]; j <= a[n]; j++) {
            f[j] = f[j] | f[j - a[i]];
        }
    }
    cout << ans << endl;
}
return 0;

}