#include <bits/stdc++.h>
using namespace std;
   struct node{
    int lc,rc,quan,id;
    bool yezi;
    
};
int main() {
    int m;
    cin>>m;
    while(m--){
  node   no[2005];
int sz[2005];
int depth[2005];
int vis[2005];
        memset(no, 0, sizeof(no));
        memset(vis,0,sizeof(vis));
           memset(depth,0,sizeof(depth));
         memset(sz,0,sizeof(sz));
        int n;
    cin>>n;
   // int tp;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    
    for(int i=1;i<=n;i++){
        cin>>sz[i];
    }
    sort(sz+1,sz+n+1);
       for(int i=1;i<=n;i++){
    
        no[i].quan=sz[i];
        no[i].yezi=1;
            no[i].id=i;
           q.push({sz[i],i});
    }
    int counter=n+1;
    while(q.size()>=2){
        auto k1=q.top();
        q.pop();
        auto k2=q.top();
        q.pop();
        no[counter].quan=k1.first+k2.first;
         no[counter].id=counter;
           no[counter].lc=k1.second;
           no[counter].rc=k2.second;
        q.push({ no[counter].quan,counter});
        counter++;
    }
    auto gen=q.top().second;
    queue<pair<int,int> >q2;
    q2.push({gen,0});
   vis[gen]=1;
    while(!q2.empty()){
        auto dep=q2.front().second;
        auto noo=q2.front().first;
		q2.pop();
        if(no[noo].lc!=0&&!vis[no[noo].lc]){
            q2.push({no[noo].lc,dep+1});
            vis[no[noo].lc]=1;
            depth[no[noo].lc]=dep+1;
        }
          if(no[noo].rc!=0&&!vis[no[noo].rc]){
            q2.push({no[noo].rc,dep+1});
            vis[no[noo].rc]=1;
             depth[no[noo].rc]=dep+1;
        }
    }
    int total=0;
    for(int i=1;i<=n;i++){
        total+=no[i].quan*depth[i];
    }
    cout<<total<<endl;
        
    }

    return 0;
}