在网友的国度*有?n?种不同面额的货币，第?i?种货币的面额为?a[i]，你可以假设每一种货币都有无穷多张。
为了方便，我们把货币种数为?n、面额数组为?a[1..n]?的货币系统记作?(n,a)。
在一个完善的货币系统中，每一个非负整数的金额?x?都应该可以被表示出，即对每一个非负整数?x，都存在?n?个非负整数?t[i]?满足?a[i]×t[i]?的和为?x。
然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额?x?不能被该货币系统表示出。
例如在货币系统?n=3,?a=[2,5,9]?中，金额?1,3?就无法被表示出来。
两个货币系统?(n,a)?和?(m,b)?是等价的，当且仅当对于任意非负整数?x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统?(m,b)，满足?(m,b)?与原来的货币系统?(n,a)?等价，且?m?尽可能的小。
他们希望你来协助完成这个艰巨的任务：找到最小的?m。
输入格式
输入文件的第一行包含一个整数?T，表示数据的组数。
接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数?n。
接下来一行包含?n?个由空格隔开的正整数?a[i]。
输出格式
输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与?(n,a)?等价的货币系统?(m,b)?中，最小的?m。
数据范围
1≤n≤100,
1≤a[i]≤25000,
1≤T≤20
输入样例：
2
4
3 19 10 6
5
11 29 13 19 17
输出样例：
2
5
这一题首先发现一个重要的性质，b里的m个数都是从a里面选的，如果b里的某个数不是从a里面选，设该数为x，由于两个数组可以互相表示，x可以表示为若干ai的代数和，又因为ai又能被bi表示，x即能被其他bi表示，即x是多余的，这样的x在b数组中是不存在的。
由于大的数可能被小的数表示，把每一个数想象成背包的体积，然后小的数就是不同体积的物品，恰好把背包填满，如果方法数为0，即加入b数组中。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 101, M = 25010;
int f[M];
int a[N];
int n;
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
sort(a, a + n);
memset(f, 0, sizeof f);
f[0] = 1;
int ans = 0;
for (int i = 0; i < n; i++)
{
if (!f[a[i]])ans++;
for (int j = a[i]; j <= a[n - 1]; j++) {
f[j] += f[j - a[i]];
}
}
cout << ans << endl;
}
}