#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); const int MAX = 1e6 + 7; int info[MAX]; bool dp[MAX]; int main() { IOS; int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> info[i]; sort(info + 1, info + 1 + n); memset(dp, 0, sizeof dp); dp[0] = 1; int ans = n; for (int i = 1; i <= n; i++) { if (dp[info[i]]) { ans--; continue; } for (int j = info[i]; j <= info[n]; j++) dp[j] |= dp[j - info[i]]; } cout << ans << endl; } return 0; } //D