// f[i][j]:现在选了i个数，且和为j能否凑成
//
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int f[110][20010];
bool check(int x) {
    int sum = 0, t = x;
    while (t) {
        sum += t % 10;
        t /= 10;
    }
    int sx = sqrt(x);
    int sn = sqrt(sum);
    if (sx * sx == x && sn * sn == sum) {
        return true;
    } else {
        return false;
    }
}
void init() {
    
}
int main() {
    init();
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            sum += x;
        }
        if (f[n][sum]) {
            cout << n << '\n';
        } else {
            cout << n - 1 << '\n';
        }
    }
    return 0;
}