#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int t,n,data[1005],m,result,tmp1,tmp2;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&data[i]);
        }
        sort(data,data+n);
        m = n;
        result = 0;
        while(true){
            if(m>3){
                tmp1 = 2*data[1]+data[0]+data[m-1];
                tmp2 = data[m-1]+data[m-2]+2*data[0];
                result += min(tmp1,tmp2);
                m-=2;
                continue;
            }
            if(m==1)result += data[0];
            if(m==2)result += data[1];
            if(m==3)result += data[0]+data[1]+data[2];
            break;
        }
        printf("%d\n",result);
    }
    return 0;
}