#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int min(int x,int y)
{
	if(x<y)
		return x;
	else
		return y;
}
int main()
{
	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		int a[1010];
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		int ans=0;
		while(n>0)
		{
			if(n==1)
				ans+=a[1];
			else if(n==2)
				ans+=a[2];
			else if(n==3)
			{
				ans+=min((a[3]+a[2]+a[1]),a[3]+2*a[2]);
				n-=2;
			}
			else
				ans+=min(2*a[1]+a[n]+a[n-1],a[n]+2*a[2]+a[1]);
			n-=2;
		}
		printf("%d\n",ans);
	}
	return 0;
}