#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

struct node{
	node *left, *right;
	int weight;
} pool[200002];

struct push_node{
	int bh;
	int weight;
};

bool operator<(const node &n1, const node &n2){
	return n1.weight > n2.weight;
}

bool operator<(const push_node &pn1, const push_node &pn2){
	return pn1.weight > pn2.weight;
}

int getSum(node *root, int depth){
	if(root->left){
		return getSum(root->left, depth+1) + getSum(root->right, depth+1);
	}
	return root->weight * depth;
}

int main() {
	int T;
	scanf("%d", &T);
	for(int ii = 0; ii < T; ii++){
		int n;
		scanf("%d", &n);
		int poolCnt = 0;
		priority_queue<push_node> pq;
		for(int i = 0; i < n; i++){
			int temp;
			scanf("%d", &temp);
			pool[poolCnt].weight = temp;
			pool[poolCnt].left = NULL;
			pool[poolCnt].right = NULL;
			push_node pn;
			pn.bh = poolCnt;
			pn.weight = temp;
			pq.push(pn);
			poolCnt++;
		}
		node *root;
		for(int i = 0; i < n-1; i++){
			push_node pn1 = pq.top();
			pq.pop();
			push_node pn2 = pq.top();
			pq.pop();
			pool[poolCnt].weight = pn1.weight + pn2.weight;
			pool[poolCnt].left = &pool[pn1.bh];
			pool[poolCnt].right = &pool[pn2.bh];
			if(i == n-2){
				root = &pool[poolCnt];
			}
			else{
				push_node pn;
				pn.bh = poolCnt;
				pn.weight = pool[poolCnt].weight;
				pq.push(pn);
			}
			poolCnt++;
		}
		printf("%d\n", getSum(root, 0));
	}
	return 0;
}