#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 <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; }


/*
  topdown
  ((o o) ((o o) o))
      3      
     / \     
    *   2    +2^2
    |   |\   
    1   1 *  +2^1 +2^1
   /|  /| |  
  0 0 0 0 0  
  -(N-2) later
  
  multiset S
  choose T \subseteq S
  S <- S \cup (T + 1)
  cost <- 2 cost + |T|
  
  should choose |T| smallest elements
*/

/*
  (ans for N = 2^K) <= K 2^(K-1) W + K 2^K
  K = 7, W = 10^9: < 10^12
*/
constexpr Int INF = 1001001001001LL;

// second[x]: weight x times
using Info = pair<Int, vector<int>>;
vector<Info> dp[110];
void build(int N) {
  dp[1].push_back(Info(0, {1}));
  dp[2].push_back(Info(0, {1, 1}));
  for (int n = 2; n <= N; ++n) {
if(n%10==0)cerr<<n<<": |dp[n]| = "<<dp[n].size()<<endl;
    {
      sort(dp[n].begin(), dp[n].end(), [&](const Info &f, const Info &g) -> bool {
        return ((f.first != g.first) ? (f.first < g.first) : (f.second > g.second));
      });
      auto dominates = [&](Info f, Info g) -> bool {
        if (f.first > g.first) return false;
        int now = 0;
        int x = 0, y = 0;
        for (int i = 0; i < n; ) {
          for (; !f.second[x]; ++x) {}
          for (; !g.second[y]; ++y) {}
          const int t = min(f.second[x], g.second[y]);
          now += t * (x - y);
          if (now > 0) return false;
          f.second[x] -= t;
          g.second[y] -= t;
          i += t;
        }
        return true;
      };
      vector<Info> fs;
      for (const Info &g : dp[n]) {
        bool ok = true;
        for (int j = fs.size(); --j >= 0; ) {
          if (dominates(fs[j], g)) {
            ok = false;
            break;
          }
        }
        if (ok) {
          fs.push_back(g);
        }
      }
      dp[n].swap(fs);
    }
if(n%10==0)cerr<<n<<": |dp[n]| = "<<dp[n].size()<<endl;
    for (const Info &f : dp[n]) {
      const int len = f.second.size();
      int nn = n;
      Info g = f;
      g.first *= 2;
      for (int i = 0; i < len; ++i) {
        if (i == len - 1) {
          g.second.push_back(0);
        }
        for (int x = 0; x < f.second[i]; ++x) {
          if (++nn > N) goto done;
          if (++g.first >= INF) goto done;
          ++g.second[i + 1];
          dp[nn].push_back(g);
        }
      }
     done:{}
    }
  }
}

int main() {
  int T;
  // for (; ~scanf("%d", &T); ) {
  scanf("%d", &T);
  {
    vector<int> Ns(T);
    vector<vector<Int>> Ws(T);
    for (int t = 0; t < T; ++t) {
      int &N = Ns[t];
      auto &W = Ws[t];
      scanf("%d", &N);
      W.resize(N);
      for (int i = 0; i < N; ++i) {
        scanf("%lld", &W[i]);
      }
      sort(W.begin(), W.end());
    }
cerr<<"Ns = "<<Ns<<endl;
    
    const int maxN = *max_element(Ns.begin(), Ns.end());
    build(maxN);
    
    for (int t = 0; t < T; ++t) {
      const int N = Ns[t];
      const auto &W = Ws[t];
      Int ans = INF;
      for (const Info &f : dp[N]) {
        Int cost = f.first * 2 - max(N - 2, 0);
        auto g = f;
        int x = 0;
        for (int i = 0; i < N; ++i) {
          for (; !g.second[x]; ++x) {}
          --g.second[x];
          cost += x * W[N - 1 - i];
        }
        chmin(ans, cost);
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}