#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;
}