#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr Int INF = 1001001001001001001LL;

int N;
vector<Int> W;


namespace brute {
Int dp[1 << 12][13];
Int run() {
cerr<<"[brute::run]"<<endl;
  vector<Int> WSum(1 << N, 0);
  for (int u = 0; u < N; ++u) {
    for (int p = 0; p < 1 << u; ++p) {
      WSum[p | 1 << u] = WSum[p] + W[u];
    }
  }
  for (int p = 0; p < 1 << N; ++p) {
    fill(dp[p], dp[p] + (N + 1), INF);
  }
  for (int u = 0; u < N; ++u) {
    dp[1 << u][0] = 0;
  }
  for (int p = 1; p < 1 << N; ++p) {
    for (int q = p; --q &= p; ) {
      for (int a = 0; a < N; ++a) for (int b = 0; b < N; ++b) {
        chmin(dp[p][max(a, b) + 1], dp[p - q][a] + dp[q][b] + ((1LL<<min(a,b))-1) + WSum[p]);
      }
    }
  }
  Int ans = INF;
  for (int a = 0; a <= N; ++a) {
    chmin(ans, dp[(1 << N) - 1][a]);
  }
  return ans;
}
}  // brute


namespace greedy {
Int run() {
cerr<<"[greedy::run]"<<endl;
  using Entry = pair<Int, Int>;
  priority_queue<Entry, vector<Entry>, greater<Entry>> que;
  for (int u = 0; u < N; ++u) {
    que.emplace(W[u], 0);
  }
  Int ans = 0;
  for (int i = 0; i < N - 1; ++i) {
    const auto a = que.top(); que.pop();
    const auto b = que.top(); que.pop();
    ans += a.first + b.first + min(a.second, b.second);
    que.emplace(a.first + b.first, min(2 * max(a.second, b.second) + 1, INF));
  }
  return ans;
}
}  // greedy


int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    W.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%lld", &W[u]);
    }
    sort(W.begin(), W.end());
    
    const Int ans = greedy::run();
    printf("%lld\n", ans);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}