// 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;
}
enum { W = 400 };
static unsigned long long bs[W];
int nw = (mx >> 6) + 1;
for (int j = 0; j < nw; j++) bs[j] = 0;
bs[0] = 1;
int ans = 0;
for (int i = 0; i < n; i++) {
int v = a[i];
if ((bs[v >> 6] >> (v & 63)) & 1) continue;
ans++;
for (int sh = v; sh <= mx; sh <<= 1) {
int ws = sh >> 6, b = sh & 63;
if (ws >= nw) break;
if (b == 0) {
for (int j = nw - 1; j >= ws; j--) bs[j] |= bs[j - ws];
} else {
for (int j = nw - 1; j >= ws; j--) {
unsigned long long x = bs[j - ws] << b;
if (j - ws - 1 >= 0) x |= bs[j - ws - 1] >> (64 - b);
bs[j] |= x;
}
}
}
}
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;
}