#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;typedef long long ll;struct Node { ll a, q; Node(ll aa=0, ll qq=0): a(aa), q(qq) {} bool operator < (const Node & _q) const { return q > _q.q; }};void gao() { int n; scanf("%d", &n); int x; priority_queue<Node> Q; for(int i=0; i<n; i++) { scanf("%d", &x); Q.push(Node(0, (ll)x)); } Node p, q; ll ans; while(!Q.empty()) { p = Q.top(); Q.pop(); if(Q.empty()) { ans = q.a; break; } q = Q.top(); Q.pop(); q.a = p.a + p.q + q.a + q.q; q.q = p.q + q.q; Q.push(q); } cout << ans << endl;}int main(){ int T; scanf("%d", &T); for(int kase=1; kase<=T; kase++) { gao(); if(kase != T) printf("n"); } return 0;}
