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


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

int N;
vector<Int> W;


namespace brute {
constexpr int MAX_N = 13;
Int WSum[1 << MAX_N];
Int dp[1 << MAX_N][MAX_N];
Int run() {
  for (int i = 0; i < N; ++i) {
    for (int p = 0; p < 1 << i; ++p) {
      WSum[p | 1 << i] = WSum[p] + W[i];
    }
  }
  for (int p = 0; p < 1 << N; ++p) {
    fill(dp[p], dp[p] + N, INF);
  }
  for (int i = 0; i < N; ++i) {
    dp[1 << i][0] = 0;
  }
  for (int p = 0; p < 1 << N; ++p) {
    for (int q = p; --q &= p; ) {
      const int limE = __builtin_popcount(q);
      const int limF = __builtin_popcount(p - q);
      for (int e = 0; e < limE; ++e) for (int f = 0; f < limF; ++f) {
        chmin(dp[p][max(e, f) + 1], dp[q][e] + dp[p - q][f] + WSum[q] + ((1LL << e) - 1) + ((1LL << f) - 1));
      }
    }
  }
  Int ans = INF;
  for (int e = 0; e < N; ++e) {
    chmin(ans, dp[(1 << N) - 1][e]);  
  }
  return ans;
}
}  // brute


namespace one {
constexpr int E = 40;
Int dp[110][E + 1];
Int run() {
  for (int n = 0; n <= N; ++n) {
    fill(dp[n], dp[n] + (E + 1), INF);
  }
  dp[1][0] = 0;
  for (int n = 2; n <= N; ++n) {
    for (int a = 1; a < n; ++a) {
      for (int e = 0; e < E; ++e) for (int f = 0; f < E; ++f) {
        chmin(dp[n][max(e, f) + 1], dp[a][e] + dp[n - a][f] + a + ((1LL << e) - 1) + ((1LL << f) - 1));
      }
    }
  }
  Int ans = INF;
  for (int e = 0; e <= E; ++e) {
    chmin(ans, dp[N][e]);
  }
  return ans;
}
}  // one


namespace slow {
constexpr int E = 40;
// second[x]: weight x times
using Info = pair<Int, vector<int>>;
vector<Info> dp[110][E + 1];
void build(int N) {
  for (int n = 0; n <= N; ++n) for (int e = 0; e <= E; ++e) {
    dp[n][e].clear();
  }
  dp[1][0].push_back(Info(0, vector<int>{1}));
  for (int n = 2; n <= N; ++n) {
    auto dominates = [&](Info f, Info g) -> bool {
      if (f.first > g.first) return false;
      int sumF = 0, sumG = 0;
      int posF = 0, posG = 0;
      for (int i = 0; i < n; ) {
        for (; !f.second[posF]; ++posF) {}
        for (; !g.second[posG]; ++posG) {}
        const int t = min(f.second[posF], g.second[posG]);
        sumF += t * posF;
        sumG += t * posG;
        if (sumF > sumG) return false;
        f.second[posF] -= t;
        g.second[posG] -= t;
        i += t;
      }
      return true;
    };
    for (int a = 1; a < n; ++a) {
      for (int ea = 0; ea < E; ++ea) for (int eb = 0; eb < E; ++eb) {
        const int e = max(ea, eb) + 1;
        const Int cost = ((1LL<<ea)-1) + ((1LL<<eb)-1);
        for (const Info &fa : dp[a][ea]) for (const Info &fb : dp[n - a][eb]) {
          Info g(fa.first + fb.first + cost,
                 vector<int>(max(fa.second.size() + 1, fb.second.size()), 0));
          for (int x = 0; x < (int)fa.second.size(); ++x) g.second[x + 1] += fa.second[x];
          for (int x = 0; x < (int)fb.second.size(); ++x) g.second[x    ] += fb.second[x];
          dp[n][e].push_back(g);
        }
      }
    }
    for (int e = 0; e <= E; ++e) {
      sort(dp[n][e].begin(), dp[n][e].end(), [&](const Info &f, const Info &g) -> bool {
        return ((f.first != g.first) ? (f.first < g.first) : (f.second > g.second));
      });
      dp[n][e].erase(unique(dp[n][e].begin(), dp[n][e].end()), dp[n][e].end());
      {
        vector<Info> tmp;
        for (const Info &f : dp[n][e]) {
          bool ok = true;
          for (const Info &g : tmp) {
            if (dominates(g, f)) {
              ok = false;
              break;
            }
          }
          if (ok) {
            tmp.push_back(f);
          }
        }
        dp[n][e].swap(tmp);
      }
// if(!dp[n][e].empty())cerr<<"dp["<<n<<"]["<<e<<"] = "<<dp[n][e]<<endl;
    }
int mx=0,sum=0;
for(int e=0;e<=E;++e){chmax(mx,(int)dp[n][e].size());sum+=(int)dp[n][e].size();}
if(n%10==0)cerr<<n<<": "<<mx<<" "<<sum<<endl;
  }
}
Int run() {
  Int ans = INF;
  for (int e = 0; e <= E; ++e) {
    for (const Info &f : dp[N][e]) {
      Info g = f;
      Int cost = g.first;
      int pos = 0;
      for (int i = 0; i < N; ++i) {
        for (; !g.second[pos]; ++pos) {}
        cost += pos * W[N - 1 - i];
        --g.second[pos];
      }
      chmin(ans, cost);
    }
  }
  return ans;
}
}  // slow


int main() {
  int T;
  for (; ~scanf("%d", &T); ) {
    vector<int> Ns(T);
    vector<vector<Int>> Ws(T);
    for (int t = 0; t < T; ++t) {
      scanf("%d", &Ns[t]);
      Ws[t].resize(Ns[t]);
      for (int i = 0; i < Ns[t]; ++i) {
        scanf("%lld", &Ws[t][i]);
      }
      sort(Ws[t].begin(), Ws[t].end());
    }
    
    const int maxN = *max_element(Ns.begin(), Ns.end());
    bool allOne = true;
    for (int t = 0; t < T; ++t) allOne = allOne && (Ws[t] == vector<Int>(Ns[t], 1));
cerr<<"Ns = "<<Ns<<", maxN = "<<maxN<<", allOne = "<<allOne<<endl;
    
    if (!allOne) {
      slow::build(maxN);
    }
    
    for (int t = 0; t < T; ++t) {
      N = Ns[t];
      W = Ws[t];
      Int ans = -1;
      if (W == vector<Int>(N, 1)) {
        ans = one::run();
      } else {
        ans = slow::run();
      }
      printf("%lld\n", ans);
#ifdef LOCAL
if(N<=brute::MAX_N){
 const Int brt=brute::run();
 if(brt!=ans)cerr<<N<<" "<<W<<": "<<brt<<" "<<ans<<endl;
 assert(brt==ans);
}
#endif
    }
  }
  return 0;
}