#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 1000005;

int z, i, n, ok[N], a, j;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> z;
while(z--) {
	cin >> n;
	for (i=0;i<=n;i++) ok[i] = 0;
	ok[0] = 1;
	for (j=0;j<n;j++) {
		cin >> a;
		for (i=n-a;i>=0;i--) if (ok[i]) ok[i + a] = 1;
	}
	for (i=n;i>=0;i--) if (ok[i]) break;
	cout << i << endl;
}
return 0;
}