#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <map>
#include <sstream>
#include <stack>
#include <bitset>
#include <random>

using ll = long long;

using namespace std;

constexpr int nm = 50002;

int n;
int a[nm];

void solve() {
    cin >> n;
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] <= n) cnt[a[i]]++;
    }

    vector<int> b;
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] > 2) {
            int x = (cnt[i] - 1) / 2;
            if (2 * i <= n) cnt[2 * i] += x;
            cnt[i] -= 2 * x;
        }
        for (int j = 0; j < cnt[i]; ++j) b.push_back(i);
    }

    int m = b.size();
    vector<bool> dp(n + 1);
    dp[0] = 1;
    for (int i = 0; i < m; ++i) {
        for (int j = n; j >= b[i]; --j) {
            dp[j] = dp[j] || dp[j - b[i]];
        }
    }

    for (int i = n; i >= 0; --i) {
        if (dp[i]) {
            cout << i << "\n";
            return;
        }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}