#include<bits/stdc++.h>
using namespace std; 
int a[2100]; 
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+n+1);  
        int sum=0;  
        while(n>=4)
        {
        	int t1=2*a[1]+a[n]+a[n-1];
        	int t2=2*a[2]+a[1]+a[n];
			if(t1>t2) sum+=t2;else sum+=t1;  
/*
第一种方案：让速度第一快的和最慢的先过去(+a[n])，第一快的送回通行证(+a[1]），
            再和第二慢的一起过去（+a[n-1]) ，第一快的再回来 (+a[1]) 
第二种方案：让速度第二快的和第一快的先过去（+a[2]），第一快的送回通行证(+a[1])，
            第二慢和最慢的一起过去(+a[n])，第二快的再回来(+a[2]) 
*/
			n-=2;//送走了两个，剩下的少两个  
		}
		  
        if(n==3) sum+=a[1]+a[2]+a[3];//最快的的和最慢的先走（+a[3]）,最快的回来（+a[1]），最快的和最慢的一起走（+a[2]）  
        else if(n==2) sum+=a[2];  //直接最快的和第二快的一起走 
        else sum+=a[1];  
        printf("%d\n",sum);  
    }  
    return 0;  
}