#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<vector<int>, vector<int>>> bs;
typedef vector<pair<vector<int>, ll>> bs2;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 105;
const int LOG = 20;
const ll inf = 1e18;
const int inf2 = 1e9;
const double eps = 1e-11;
void print(int x) {
    cout << x;
}

template <class T>
void printa(vector<T> a) {
    int n = a.size();
    cout << "[";
    for (int i = 0; i < n; i++) {
        print(a[i]);
        cout << (i < n - 1 ? ", " : "");
    }
    
    cout << "]\n";
}

int w[N];
vector<bs> plans;
ll out = inf;
int cnt = 0;
map<bs2, ll> mp;
void dfs(bs2 a, bs plan, ll c) {
    if (c > inf) return;
    int n = a.size();
    sort(a.begin(), a.end());
    if (mp.contains(a) && mp[a] <= c) return;
    mp[a] = c, cnt++;
    if (n == 1) {
        if (c < out) plans.clear();
        if (c <= out) {
            out = c;
            plans.push_back(plan);
        }
        
    }
    
    int s = inf2, ss = inf2;
    for (int i = 0; i < n; i++) {
        int sz = a[i].first.size();
        if (sz < s) s = sz;
        else if (sz < ss) ss = sz;    
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int sz1 = a[i].first.size(), sz2 = a[j].first.size();
            if ((s == sz1 && ss == sz2) || (s == sz2 && ss == sz1)) {
                bs2 b;
                bs planb = plan;
                ll cb = c, wb = 0;
                vector<int> v;
                for (int k = 0; k < n; k++) {
                    if (i != k && j != k) {
                        b.push_back(a[k]);
                    }
                    
                    if (i == k || j == k) {
                        for (int x : a[k].first) {
                            v.push_back(x);
                            if (i == k) cb += w[x];
                        }
                        
                        cb += a[k].second, wb = max(wb, a[k].second);
                    }
                }
                
                sort(v.begin(), v.end());
                b.push_back({v, wb * 2 + 1});
                planb.push_back({a[i].first, a[j].first});
                dfs(b, planb, cb);
            }
        }
    }
}

int n, m, k, qq;
void solve() {
    cnt = 0, out = inf;
    plans.clear();
    mp.clear();
    cin >> n;
    bs2 a(n);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        a[i - 1].first.push_back(i), a[i - 1].second = 0;
    }
    
    bs plan;
    dfs(a, plan, 0);
    cout << out << "\n";
    // cout << "------------------------------\n";
    // cout << cnt << " " << "\n";
    // for (bs v : plans) {
    //     for (auto p : v) {
    //         auto [vi, vj] = p;
    //         printa(vi);
    //         printa(vj);
    //         cout << "****\n";
    //     }
        
    //     cout << "------****------\n";
    // }
    
    // cout << "------------------------------\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}