#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int i,t,n,data[1005],ans,x,y;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&data[i]);
        sort(data,data+n);
        ans = 0;
        while(n>3){
            x = data[n-1]+data[0]+data[n-2]+data[0];
            y = data[1]+data[0]+data[n-1]+data[1];
            ans += min(x,y);
            n -= 2;
        }
        if(n==3)ans += data[1]+data[0]+data[2];
        if(n==2)ans += data[1];
        if(n==1)ans += data[0];
        printf("%d\n",ans);
    }
    return 0;
}