// This code is AI-generated. (AI 生成的代码)
// NOIP2018 货币系统: sort denominations; a denomination is redundant iff it is
// representable by the already kept (smaller) ones. Mark reachable sums with a
// complete-knapsack update whenever a denomination is kept.
#include <stdio.h>
#include <string.h>
static int a[105];
static char can[25005];
static char buf[1 << 16], ob[1 << 10];
static char *gp;
int main() {
int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = 0; gp = buf;
char *op = ob;
#define RD(dst) do { while (*gp < '0') gp++; int v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0'); dst = v; } while (0)
int T; RD(T);
while (T--) {
int n; RD(n);
int mx = 0;
for (int i = 0; i < n; i++) { RD(a[i]); if (a[i] > mx) mx = a[i]; }
for (int i = 1; i < n; i++) {
int x = a[i], j = i - 1;
while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
a[j + 1] = x;
}
memset(can, 0, mx + 1);
can[0] = 1;
int ans = 0;
for (int i = 0; i < n; i++) {
if (can[a[i]]) continue;
ans++;
int v = a[i];
for (int j = v; j <= mx; j++)
if (can[j - v]) can[j] = 1;
}
char t[8]; int k = 0;
if (!ans) t[k++] = '0';
while (ans) { t[k++] = (char)('0' + ans % 10); ans /= 10; }
while (k) *op++ = t[--k];
*op++ = '\n';
}
fwrite(ob, 1, op - ob, stdout);
return 0;
}