#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1024];
int main(){
	int t;
	int n;
	while(scanf("%d",&t)==1){
		while(t--){
			int total1=0,total2=0;
			scanf("%d",&n);
			for(int i=0;i<n;i++)
				scanf("%d",&a[i]);
			sort(a,a+n);
			if(n<3)	printf("%d\n",a[n-1]);
			else if(n==3)	printf("%d\n",a[0]+a[1]+a[2]);
			else{
				if(n%2==0){
					for(int j=1;j<n;j++)
						total1+=a[j];
					total1=total1+(n-2)*a[0];
					total2=(a[0]+a[1])*(n/2-1)+a[1];
					for(int j=n-1;j>=2;j-=2)
						total2+=a[j]+a[1];
					printf("%d\n",total1>total2? total2 : total1);
				}
				else{
						for(int j=1;j<n;j++)
							total1+=a[j];
						total1=total1+(n-2)*a[0];
						total2=(a[0]+a[1])*(n/2);
						for(int j=n-1;j>=3;j-=2)
							total2+=a[j]+a[1];
						total2+=a[2];
						printf("%d\n",total1>total2? total2 : total1);
				}

			}
		}

	}
	return 0;
}