#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

constexpr int N = 105;
constexpr int LG = 41;

int64_t shit[10];

std::vector<std::pair<std::string, int64_t>> dp[N][LG];

std::mt19937 rnd;
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
    std::sort(vec.begin(), vec.end());

    std::list<std::remove_reference_t<decltype(vec[0])>> list;
    for (auto& s : vec) {
        list.emplace_front(std::move(s.first), s.second);
    }
    // list.reverse();
    // for (int k : std::array{2}) {
    //     for (auto it = list.begin(); it != list.end(); it++) {
    //         int dlt = 0;
    //         for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
    //             if (it->second <= it2->second) {
    //                 dlt++;
    //                 bool fk = true;

    //                 int sz = std::min(it->first.size(), it2->first.size());
    //                 for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
    //                     sm1 += it->first[t];
    //                     sm2 += it2->first[t];
    //                     fk &= sm1 >= sm2;
    //                 }
    //                 if (fk) {
    //                     shit[k != 2]++;

    //                     it2--;
    //                     dlt--;
    //                     list.erase(std::next(it2));
    //                 }
    //             }
    //         }
    //     }
    // }
    for (int k : std::array{2}) {
        for (auto it = list.begin(); it != list.end(); it++) {
            int dlt = 0;
            for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
                if (it->second <= it2->second) {
                    dlt++;
                    bool fk = true;

                    int sz = std::min(it->first.size(), it2->first.size());
                    for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
                        sm1 += it->first[t];
                        sm2 += it2->first[t];
                        fk &= sm1 >= sm2;
                    }
                    if (fk) {
                        shit[k != 2]++;

                        it2--;
                        dlt--;
                        list.erase(std::next(it2));
                    }
                }
            }
        }
    }
    vec.assign(list.begin(), list.end());
    vec.shrink_to_fit();
}

void clear_vec1(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end(), [&](const auto& a, const auto& b) { return a.first == b.first; }), vec.end());

    int cnt = 0;
    for (int i = 0; i < vec.size(); i++) {
        for (int j = i + 1; j < vec.size(); j++) {
            if (vec[i].second <= vec[j].second) {
                bool fk = true;
                for (int t = 0; t < s; t++) {
                    fk &= vec[i].first[t] <= vec[j].first[t];
                }
                if (fk) {
                    vec.erase(vec.begin() + j);
                    j--;
                    cnt++;
                }
            }
        }
    }
    vec.shrink_to_fit();
    if (cnt > 100 || vec.size() > 100) {
        // std::cerr << "cleared: " << cnt << "  " << vec.size() << "\n";
    }
}

void clear_vec2(int s, const std::vector<std::pair<std::string, int64_t>>& vec0, std::vector<std::pair<std::string, int64_t>>& vec) {
    int cnt = 0;

    for (int i = 0; i < vec0.size(); i++) {
        for (int j = 0; j < vec.size(); j++) {
            if (vec0[i].second <= vec[j].second) {
                bool fk = true;
                for (int t = 0; t < s; t++) {
                    fk &= vec0[i].first[t] <= vec[j].first[t];
                }
                if (fk) {
                    vec.erase(vec.begin() + j);
                    j--;
                    cnt++;
                }
            }
        }
    }
    vec.shrink_to_fit();
    if (cnt > 0) {
        std::cerr << "cleared_fuck: " << cnt << "\n";
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;

    int t;
    std::cin >> t;
    std::vector<std::vector<int>> inputs(t);
    for (auto& vec : inputs) {
        int k;
        std::cin >> k;
        vec.resize(k);
        for (auto& i : vec) {
            std::cin >> i;
        }
        n = std::max(n, k);
    }

    dp[1][0] = {{std::string(1, 1), 0}};
    for (int s = 2; s <= n; s++) {
        std::vector<int> ord(s - 1);
        std::iota(ord.begin(), ord.end(), 1);
        std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });

        for (int k = 0; k < LG; k++) {
            static std::unordered_map<std::string, int64_t> map;
            // static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
            map.clear();

            for (int k1 = 0; k1 < LG; k1++) {
                for (int k2 = 0; k2 < LG; k2++) {
                    if (k != std::max(k1, k2) + 1) {
                        continue;
                    }
                    for (int s1 : ord) {
                        int s2 = s - s1;
                        if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
                            continue;
                        }
                        if (k >= LG) {
                            continue;
                        }

                        for (auto [v1, c1] : dp[s1][k1]) {
                            for (auto [v2, c2] : dp[s2][k2]) {
                                v2.resize(std::max(v2.size(), v1.size() + 1));
                                for (int i = 0; i < v1.size(); i++) {
                                    v2[i + 1] += v1[i];
                                }
                                int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
                                // dp[s][k].push_back({all, cost});
                                auto [it, suc] = map.insert({v2, cost});
                                if (!suc) {
                                    it->second = std::min(it->second, cost);
                                }
                            }
                        }
                    }
                }
            }
            auto& vec = dp[s][k];
            vec.assign(map.begin(), map.end());
            clear_vec(s, dp[s][k]);
        }

        {
            int i = s;
            std::cerr << i << "  ";
            // std::cerr << i << "   ";
            // for (int j = 0; j < LG; j++) {
            //     std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
            // }
            std::cerr.flush();
        }
    }

    int64_t total_sum = 0;
    for (int i = 1; i <= n; i++) {
        // std::cerr << i << "   ";
        for (int j = 0; j < LG; j++) {
            // std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
            total_sum += dp[i][j].size();
        }
    }
    std::cerr << "total: " << total_sum << std::endl;
    std::cerr << shit[0] << " " << shit[1] << "\n";

    for (auto& vec : inputs) {
        int m = vec.size();
        int64_t ans = 1e18;
        std::sort(vec.begin(), vec.end());
        for (int k = 0; k < LG; k++) {
            for (auto [vc2, ct] : dp[m][k]) {
                std::vector<char> vc;
                for (int i = 0; i < vc2.size(); i++) {
                    vc.insert(vc.end(), vc2[i], i);
                }
                int64_t res = 0;
                res += ct;
                for (int i = 0; i < m; i++) {
                    res += vec.rbegin()[i] * int64_t(vc[i]);
                }
                ans = std::min(ans, res);
            }
        }
        std::cout << ans << "\n";
    }

    return 0;
}