#include<bits/stdc++.h>
using namespace std;
int a[10000010];
int main()
{
	int t,ans;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	
    ans=0;
	while(n>3)
	{
		int sum1=a[1]*2+a[n]+a[n-1];
		int sum2=a[2]*2+a[1]+a[n];
		ans+=min(sum1,sum2);
		n-=2; 
	}
	    if(n==1)
	    ans+=a[1];
	    else if(n==2)
	    ans+=a[2];
		else if(n==3) 
		ans+=a[3]+a[2]+a[1]; 
	}
	cout<<ans;
	return 0;
}