#include <bits/stdc++.h>
using namespace std;

int i,t,n;

int main(){
    cin>>t;
    while(t--){
    	int a[1001];
    	cin>>n;
    	for(i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		int ans=0;
		while(n>3){
			int s1=a[1]*2+a[n]+a[n-1];
			int s2=a[1]+a[2]*2+a[n];
			ans+=min(s1,s2);
			n-=2;
		}
		if(n==3) ans+=a[1]+a[2]+a[3];
		if(n==2) ans+=a[2];
		if(n==1) ans+=a[1];
		cout<<ans<<endl;
	}
    
    return 0;
}