#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,T,i,j;
int a[1200];
int main()
{
	cin>>T;
	int i,j;
	while (T--)
	{
		cin>>n;
		for(i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		int sum=0;
		int t1=a[2]+a[1];
		sum=t1;
		if(n==1)
		{
			printf("%d\n",a[1]);
			continue;
		}
		if(n==2)
		{
			printf("%d\n",a[2]);
			continue;
		}
		for(i=3;i<=n-2;i+=2)
		{
			int q=2*a[1]+a[i]+a[i+1];
			int w=a[1]+2*a[2]+a[i+1];
			if(q<w)
				sum+=q;
			else sum+=w;
		}
		if(n%2==0&&n!=2)
		{
			int q=a[n]+2*a[2];
			int w=a[1]+a[n-1]+a[n];
			sum+=min(q,w);
		}
		if(n%2==1&&n!=1)
		{
			sum+=a[n];
		}
		printf("%d\n",sum);
	}
}