#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tag_and_trait.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// namespace gt = __gnu_pbds;
#define IS_MULTITEST 1

using namespace std;

// #include "angel/math/modint.hpp"

#pragma region Macros
// clang-format off
using ll = long long; using uint = unsigned int; using ull = unsigned long long;
using i32 = int; using i64 = ll; using u32 = uint; using u64 = ull;
using i128 = __int128_t; using u128 = __uint128_t;
using Str = string;
template <class T> using Vec = vector<T>;
template <class T> using RevPriq = priority_queue<T, vector<T>, greater<T>>;
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};
constexpr int inf32 = 1 << 30; constexpr ll inf64 = 1ll << 60;
constexpr char eoln = '\n';
#define L(i, l, r) for (int i = (l); i < (r); ++i)
#define R(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define ALL(x) (x).begin(), (x).end()
#define mem(a, x) memset((a), (x), sizeof(a))
#define sz(a) (int)((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
// clang-format on
#pragma endregion

// Coding Space

constexpr int B = 30;
int N;
Vec<ll> W, sW;
Vec<Vec<Vec<ll>>> dp;
Vec<Vec<Vec<ll>>> fldp;
Vec<Vec<Vec<int>>> lp, rp;

ll hcost(ll n) {
    if (n <= 60) return (1ll << n) - 1;
    else return inf64;
}

ll wSum(int l, int r) {
    return sW[r] - sW[l];
}

void work() {
    L(h, 0, N) {
        L(width, 0, N) {
            L(l, 0, N) {
                int r = l + width;
                if (r >= N) continue;
                if (h == 0) {
                    if (l == r) dp[l][r][h] = 0;
                    else dp[l][r][h] = inf64;
                } else if (l == r) {
                    dp[l][r][h] = inf64;
                } else if (h > r - l) {
                    dp[l][r][h] = inf64;
                } else {
                    ll xv = numeric_limits<ll>::max();
                    ll yv = xv;
                    int li = lp[l][r - 1][h] == -1 ? l : lp[l][r - 1][h];
                    int ri = lp[l + 1][r][h] == -1 ? r - 1 : lp[l + 1][r][h];
                    L(m, li, ri + 1) {
                        if (m == r) break;
                        ll ac = wSum(l, m + 1) + wSum(m + 1, r + 1) + hcost(h - 1);
                        ll lv = dp[l][m][h - 1];
                        ll rv = fldp[m + 1][r][h - 1];
                        if (xv > lv + rv + ac) {
                            xv = lv + rv + ac;
                            lp[l][r][h] = m;
                        }
                    }

                    li = rp[l][r - 1][h] == -1 ? l : rp[l][r - 1][h];
                    ri = rp[l + 1][r][h] == -1 ? r - 1 : rp[l + 1][r][h];
                    L(m, li, ri + 1) {
                        if (m == r) break;
                        ll ac = wSum(l, m + 1) + wSum(m + 1, r + 1) + hcost(h - 1);
                        ll lv = fldp[l][m][h - 1];
                        ll rv = dp[m + 1][r][h - 1];
                        if (yv > lv + rv + ac) {
                            yv = lv + rv + ac;
                            rp[l][r][h] = m;
                        }
                    }
                    dp[l][r][h] = min(xv, yv);
                }

                fldp[l][r][h] = min(fldp[l][r][h], dp[l][r][h]);
                if (h != 0) {
                    fldp[l][r][h] = min(fldp[l][r][h], fldp[l][r][h - 1] - hcost(h) + hcost(h - 1));
                }
            }
        }
    }
}

void main_() {
    cin >> N;
    W.assign(N, 0);
    for (auto &e : W) cin >> e;

    sort(ALL(W));
    sW.assign(N + 1, 0);
    L(i, 0, N) sW[i + 1] = sW[i] + W[i];

    dp.resize(N);
    lp.resize(N);
    L(i, 0, N) {
        dp[i].resize(N);
        lp[i].resize(N);
        L(j, 0, N) {
            dp[i][j].assign(N, inf64);
            lp[i][j].resize(N, -1);
        }
    }
    fldp = dp;
    rp = lp;
    ll ans = inf64;
    work();
    L(i, 0, N) {
        ans = min(ans, dp[0][N - 1][i]);
    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if constexpr (IS_MULTITEST == 0) {
        main_();
    } else {
        // multitest (cf-style)
        int T;
        cin >> T;
        while (T--) {
            main_();
            cout << flush;
        }
    }
}