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