#include <bits/stdc++.h>
using namespace std;
#define debug(a) cerr << #a << " = " << (a) << nl;
#define ll long long
#define int long long
#define nl '\n'

const int N = 5e4+5;
bitset<N> dp;
void jAVA()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    dp.reset();
    dp[0] = 1;
    for(auto i: a) dp |= dp<<i;
    int ans = 0;
    for(int i=1;i<=n;++i) {
        if(dp[i]) ans = i;
    }
    cout << ans << nl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int t = 1, cs = 0;
    cin >> t;
    while (t--){
        // cout << "Case " << ++cs << ": ";
        jAVA();
    }
    return 0;
}