//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = -1, inf = 1000111222;

void solve() {
    int n;
    cin >> n;
    vector<int> c(n);
    for(auto& x : c) cin >> x;
    set<pair<int, ll> > av;
    set<pair<ll, int> > av2;
    set<pair<ll, pair<int, int> > > av_pair;
    for(int i = 0; i < n; i++) {
        av.insert({i, c[i]});
        av2.insert({c[i], i});
        if(i - 1 >= 0) av_pair.insert({c[i - 1] + c[i], {i - 1, i}});
    }
    ll ans = 0;
    while(len(av2) > 1) {
        auto A = (*av2.begin());
        av2.erase(A);
        auto B = (*av2.begin());
        av2.erase(B);
        ans += A.fi + B.fi;
        av2.insert({A.fi + B.fi, A.se});
    }
    cout << ans << '\n';
    return;
    while(!av_pair.empty()) {
        auto cur_pair = (*av_pair.begin());
        ans += cur_pair.fi;
        av_pair.erase(cur_pair);
        auto it_fir = av.lower_bound({cur_pair.se.fi, 0});
        pair<int, ll> prv = {-1, -1};
        if(it_fir != av.begin()) {
            auto it_prv = it_fir; it_prv--;
            prv = (*it_prv);
            av_pair.erase({(*it_prv).se + (*it_fir).se, {(*it_prv).fi, (*it_fir).fi}});
        }
        auto it_sec = it_fir; it_sec++;
        auto it_nxt = it_sec;
        it_nxt++;
        pair<int, ll> nxt = {-1, -1};
        if(it_nxt != av.end()) {
            nxt = (*it_nxt);
            av_pair.erase({(*it_sec).se + (*it_nxt).se, {(*it_sec).fi, (*it_nxt).fi}});
        }
        pair<int, ll> a_fir = (*it_fir);
        pair<int, ll> a_sec = (*it_sec);
        pair<int, ll> new_guy = {a_fir.fi, a_fir.se + a_sec.se};
        av.erase(a_fir);
        av.erase(a_sec);
        av.insert(new_guy);
        if(prv.fi != -1) {
            av_pair.insert({prv.se + new_guy.se, {prv.fi, new_guy.fi}});
        }
        if(nxt.fi != -1) {
            av_pair.insert({new_guy.se + nxt.se, {new_guy.fi, nxt.fi}});
        }
    }
    cout << ans << '\n';
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/