#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1005];
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		int ans=0;
		if(n==1)printf("%d\n",a[1]);
		else if(n==2) {
			printf("%d\n",a[2]);
			continue;
		} else if(n==3) {
			printf("%d\n",a[1]+a[3]+a[2]);
		} else {int ans=0;
			for(int i=n;i>=3;i-=2){
				ans+=min(2*a[2]+a[n]+a[1],a[n]+a[n-1]+2*a[1]);
				n-=2;
			}
			if(n==1)ans-=a[1];
			else ans+=a[2];
			printf("%d\n",ans);
	}
}}