#include<bits/stdc++.h>
using  namespace std;
int n,t;
int a[1010];
int main(){
	cin>>t;
	while(t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+1+n);
		int 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 ans+=a[1]+a[2]+a[3];
		cout<<ans<<endl;
	}
	return 0;
}