#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define el '\n'

const int N = 5e4 + 1;

template<int sz>
void work (int n) {
  if (n > sz) {
    work<min(N, sz * 2)> (n);
    return;
  }
  bitset<sz + 5> b;
  b.set(0);
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    b |= b << a[i];
  }
  for (int i = n; i >= 0; i--) {
    if (b[i]) {
      cout << i << el;
      return;
    }
  }
}

void run_case(int tc) {
  int n;
  cin >> n;
  work <1> (n);
}

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int _t = 1;
  cin >> _t;
  for (int i = 1; i <= _t; i++) {
    run_case(i);
  }
}