// ! Bismillahir Rahmanir Raheem
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template < typename PB >
  using pbds = tree < PB, null_type, less < PB > , rb_tree_tag, tree_order_statistics_node_update > ;
#define Moon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

// Typedefs
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl; // vvl v(n , vl(n , 0));
typedef pair<int, int> pii;
typedef priority_queue<ll, vector<ll>, greater<ll>> GPQ;
typedef long double ld;
typedef unsigned long long ull;
typedef priority_queue<ll> PQ;

// Constants
const int inf = 2e9;
const ll INF = 9e18;
const double PI = acos(-1);
const double eps = 1e-9;
const int mod = 1e9 + 7;

// Common ops
#define sz(n) (int)n.size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define RY {cout << "YES\n"; return;}
#define RN {cout << "NO\n"; return;}
#define ff first
#define ss second
#define nl '\n'
#define sp " "
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define forcin(p) for (auto &x : p) cin >> x
#define mem(a, b) memset(a, b, sizeof(a))

// Bitwise
#define cnt_bits(x) __builtin_popcountll(x)
#define clz(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctzll(x)

// Math
#define gcd(a, b) __gcd(a, b)
#define lcm(x, y) x * (y / gcd(x, y))

// Precision
#define set_pre(a) cout.unsetf(ios::floatfield); cout.precision(a); cout.setf(ios::fixed, ios::floatfield);
#define preci(x) fixed << setprecision(x)

// Misc. functions
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define el "\n"
#define forcout(p) for (auto x : p) cout << x << ' '
#define bs binary_search


map<pii,int> dp;
vi v;
int n;

int f(int i , int sum)
{
  if(i == n || sum == 0) return 0;

  if(dp.find({i, sum}) != dp.end()) return dp[{i, sum}];
    
  int ans = 0;
  ans = f(i + 1, sum);
  if(sum >= v[i]) ans = max(ans, v[i] + f(i + 1, sum - v[i]));

  return dp[{i,sum}] = ans;
}

void solve(){
  // ll n; cin >> n;  vl v(n); forcin(v);
  
 
  cin >> n;

  v = vi(n);
  forcin(v);

  cout << f(0, n) << nl;

}

int main(){
    Moon;
    

    int t=1 , tc = 1;
    cin >> t;          
    while(t--){
       // cout << "Case " << tc++ << ": ";  //! for case
        solve();
        dp.clear();
    }

    // timeStamp;
    return 0;
}

/*
//! siv = sieve, modu = mod 
*/

/**
 * PBDS Tips:
 * - less<T>         : Sorted set (asc)
 * - less_equal<T>   : Multiset (asc)
 * - greater<T>      : Sorted set (desc)
 * - greater_equal<T>: Multiset (desc)
 *
 * name.order_of_key(k)  -> Count of elements < k
 * *name.find_by_order(k)-> k-th smallest element (0-indexed)
*/