ハフマンツリー

#include
#include
#include

using namespace std;


int main(){
    int t;
    cin>>t;
    while(t--)
{
    priority_queue,greater > q;
    int n;
    cin>>n;
    //scanf("%d",&n);
    long long temp;long long ans = 0;
    for(int i = 0 ; i < n; i ++)
    {
        scanf("%lld",&temp);
        q.push(temp);
    }
    while(q.size()>1)
    {
        long long  x = q.top();
        q.pop();
        long long  y = q.top();
        q.pop();
        q.push(x+y);
        ans +=x+y;
    }
    printf("%lld
",ans);

}
   return 0;
}