AC

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std; const int MAX_A = 25000; int main() {

int T;
cin >> T;
while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    int max_a = a.back();
    vector<bool> dp(max_a + 1, false);
    dp[0] = true;
    int res = 0;
    
    for (int i = 0; i < n; ++i) {
        if (!dp[a[i]]) {
            res++;
            for (int j = a[i]; j <= max_a; ++j) {
                if (dp[j - a[i]]) {
                    dp[j] = true;
                }
            }
        }
    }
    cout << res << endl;
}
return 0;

}