#include<stdio.h>

void sort(int a[],int n)
{
	int i,j,k,temp;
	for(i=0;i<n;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
			if(a[k]>a[j])
				k=j;
		if(k!=i)
		{
			temp=a[k];
			a[k]=a[i];
			a[i]=temp;
		}
	}
}

int get(int a[],int n)
{
	int time=0;
	if(2*a[1]>a[n-1]+a[0])
		time=a[n-1]+2*a[0]+a[n-2];
	else
		time=a[1]+a[0]+a[n-1]+a[1];
	return time;
}

main()
{
	int T,N,i,j,time=0;
	int a[1000];
	scanf("%d",&T);
	for(j=0;j<T;j++)
	{	
		scanf("%d",&N);
		time=0;
		for(i=0;i<N;i++)
			scanf("%d",&a[i]);
		sort(a,N);
		while(N)
		{
			if(N>=4){
			time+=get(a,N);
			N-=2;}
		    else if(N==2)
			{time+=a[1];break;}
		    else if(N==3)
			{time+=(a[0]+a[1]+a[2]);break;}
		    else if(N==1)
			{time+=a[0];break;}
		}
		printf("%d\n",time);
	}
	return 0;
}