#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
int N;
Vec<ll> W, sW;
Vec<Vec<Vec<ll>>> dp;
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];
}
ll sol(int l, int r, int h) {
if (h < 0) return inf64;
if (dp[l][r][h] != -1) return dp[l][r][h];
if (l == r) {
if (h == 0) return dp[l][r][h] = 0;
else return dp[l][r][h] = inf64;
}
ll ret = inf64;
L(m, l, r) {
L(ha, 0, h) {
{
ll lv = sol(l, m, h - 1);
ll rv = sol(m + 1, r, ha);
ll hc = hcost(ha);
ll ac = wSum(l, m + 1) + wSum(m + 1, r + 1);
ret = min(ret, lv + rv + hc + ac);
}
{
ll lv = sol(l, m, ha);
ll rv = sol(m + 1, r, h - 1);
ll hc = hcost(ha);
ll ac = wSum(l, m + 1) + wSum(m + 1, r + 1);
ret = min(ret, lv + rv + hc + ac);
}
}
}
return dp[l][r][h] = ret;
}
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 = Vec(N, Vec(N, Vec(N, -1ll)));
ll ans = inf64;
L(i, 0, N) {
ans = min(ans, sol(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;
}
}
}