#include<bits/stdc++.h>

using namespace std;

int a[1005];

int main(){
	
	int t,n,m1,m2,s=0;
	
	cin>>t;
	
	for(int x=1;x<=t;x++){
		
		cin>>n;
		
		for(int i=1;i<=n;i++){
			
			cin>>a[i];
		}
		
		s=0;
		
		sort(a+1,a+n+1);
		
		while(n>3){
			
			m1=0;
			
			m2=0;
			
			m1=a[1]*2+a[n]+a[n-1];
			
			m2=a[2]*2+a[1]+a[n];
			
			s=s+min(m1,m2);
			
			n=n-2;
		}
		
		if(n==3)
		s=s+a[1]+a[2]+a[3];
		
		if(n==2)
		s=s+a[2];
		
		if(n==1)
		s=s+a[1];	
		
		cout<<s<<endl;
	}
	

	return 0;
}