#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 80
#define M 7
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];
long long S[N+1],dp[N+1][N+1][M+1],ans;
int main()
{
	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]=inf;
		for (int i=1;i<=n;++i) dp[i][i][0]=0;
		for (int i=n;i>=1;--i)
			for (int j=i;j<=n;++j)
				for (int k=i;k<=j-1;++k)
					for (int t=0;t<=M-1;++t)
						for (int s=0;s<=M-1;++s)
							dp[i][j][max(t,s)+1]=min(dp[i][j][max(t,s)+1],dp[i][k][t]+dp[k+1][j][s]+S[j]-S[i-1]+t);
		for (int i=1;i<=M;++i) ans=min(ans,dp[1][n][i]);
		printf("%lld\n",ans);
	}
	return 0;
}