#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int t,n,m,p,q,ans;
int a[105],b[105];
int kk(int nn) {
	int cnt;
	if(nn==1) return a[0];
	else if(nn==2) return a[1];
	else if(nn==3) return a[0]+a[1]+a[2];
	else {
		if(2*a[1]>a[0]+a[nn-2]) {
			cnt=2*a[0]+a[nn-2]+a[nn-1];
		} else {
			cnt=a[0]+a[1]*2+a[nn-1];
		}
		return cnt+kk(nn-2);
	}
}
int main() {
	cin>>t;
	for(int k=0; k<t; k++) {
		ans=0;
		memset(a,0,sizeof(a));
		cin>>n;
		for(int i=0; i<n; i++) {
			cin>>a[i];
		}
		sort(a,a+n);
		ans=kk(n);
		cout<<ans<<endl;
	}
}