// Problem: P9483 [NOI2023] 合并书本
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9483
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 105
using namespace std;
int cnt[N],val[N],a[N];
int n,ans;
void dfs(vector<poly>g,int siz)
{
	// cout<<"!!"<<endl;
	int l=0;
	for (auto u:g.back())
		l+=u-1;
	if (l+siz>n) return;
	if (siz==n)
	{
		int res=0,pos=1,tt=0;
		for (int i=0;i<g.size();i++)
		{
			for (auto u:g[i])
			{
				tt++;
				cnt[i]++;
				res+=val[u];
				if (i!=0) res+=val[u+1]-val[u];
			}
		}
		// assert(tt==siz);
		// cout<<res<<endl;
		for (int i=0;i<=n;i++)
		{
			for (int j=1;j<=cnt[i];j++)
			{
				// cout<<i<<",";
				// cout<<"?"<<i<<" "<<a[pos]<<" "<<pos<<" "<<siz<<" "<<tt<<endl;
				res+=a[pos]*(i);
				pos++;
			}
			cnt[i]=0;
		}
		// cout<<"???"<<pos<<endl;
		// assert(pos==n+1);
		// cout<<res<<endl;
		// cout<<endl;
		ans=min(ans,res);
		return;
	}
	poly nxt;
	for (auto u:g.back())
		for (int j=1;j<u;j++) nxt.push_back(j);
	sort(nxt.begin(),nxt.end());
	g.push_back(nxt);
	if (nxt.empty()) return;
	while (1)
	{
		// for (auto u:g[(int)g.size()-2]) cout<<u<<",";
		// cout<<endl;
		// for (auto u:nxt) cout<<u<<",";
		// cout<<endl;
		// cout<<endl;
		dfs(g,siz+nxt.size());
		if (g.back().back()==1) break;
		// if (g.size()==3)
		// {
			// for (auto u:g.back()) cout<<u<<",";
			// cout<<endl;
		// }
		for (int i=(int)g.back().size()-1;i>=0;i--)
		{
			if (g.back()[i]!=g.back().back())
			{
				g.back()[i+1]--;
				break;
			}
		}
	}
	// cout<<endl;
}		
void BellaKira()
{
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	val[1]=0;
	val[2]=0;
	for (int i=3;i<=50;i++)
	{
		int now=val[i-1]-val[i-2];
		val[i]=val[i-1]+(now*2+1);
	}
	sort(a+1,a+n+1,greater<int>());
	ans=inf;
	for (int i=1;i<=50;i++)
	{
		dfs(vector<poly>(1,poly(1,i)),1);
	}
	cout<<ans<<'\n';
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	cin>>T;
	while (T--)
	{
		BellaKira();
	}
}