#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 368
#define M 40
using namespace std;
const long long inf=(long long)(1e18);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
bool cmp(int x,int y)
{
	return x>y;
}
int lowbit(int x)
{
	return x&(-x);
}
int T,n,w[N+1],lg[N+1],ps[N+1][N+1][M+1];
long long S[N+1],F[N+1][N+1][N+1],dp[N+1][N+1][M+1],ans;
int main()
{
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	T=read();
	while (T--)
	{
		n=read(),ans=inf;
		for (int i=1;i<=n;++i) w[i]=read();
		sort(w+1,w+n+1,cmp);
		for (int i=1;i<=n;++i) S[i]=S[i-1]+w[i];
		for (int i=1;i<=n;++i)
			for (int j=i;j<=n;++j)
				for (int k=0;k<=M;++k)
					dp[i][j][k]=F[i][j][k]=inf;
		for (int i=1;i<=n;++i)
			for (int j=0;j<=M;++j)
				dp[i][i][j]=F[i][i][j]=0,ps[i][i][j]=i;
		for (int i=n;i>=1;--i)
			for (int j=i+1;j<=n;++j)
				for (int k=lg[j-i+1];k<=M;++k)
				{
					for (int t=ps[i][j-1][k];t<=ps[i+1][j][k];++t)
						if (F[i][t][k-1]+dp[t+1][j][k-1]+S[j]-S[i-1]<dp[i][j][k])
							dp[i][j][k]=F[i][t][k-1]+dp[t+1][j][k-1]+S[j]-S[i-1],ps[i][j][k]=t;
					if (F[i][j][k-1]+S[j]-S[i-1]<dp[i][j][k]) dp[i][j][k]=F[i][j][k-1]+S[j]-S[i-1],ps[i][j][k]=j;
					F[i][j][k]=min(min(F[i][j][k],F[i][j][k-1]),dp[i][j][k]+(1ll<<k)-1);
				}
		for (int i=1;i<=M;++i) ans=min(ans,dp[1][n][i]);
		printf("%lld\n",ans);
	}
	return 0;
}