#include<iostream>
#include<algorithm>
#include<cstring>

typedef long long LL;
using namespace std;

const int N=1e5;
int a[N];
int T,n;
LL dp[N];

//每次过三个人，回两个人...最后一趟过三个人
/*分情况：用两个最小的数运一个最大数、回来的就是这两个小数
          用一个小数运两个大数（需要保证对面有一个小数，跟着回来）
          运过去三个数，都留在对面，对面选两个回来（需要保证对面至少有两个数）

*/
int main()
{
    cin>>T;
    while(T--)
    {
        //memset(a,0,sizeof(a));
        cin>>n;

        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
        }
        sort(a+1,a+n+1);//先对所有数字排序
        if(n<=3) cout<<a[n]<<endl;
        else
        {
            dp[n+1]=0;//每次T循环需要重新初始化为0
            for(int i=n;i>=4;i--)
            {
                //第一种情况，把第i个人运过去，其中dp[i]表示第i个人到第n个人运过去花的时间
                dp[i]=a[i]+a[2]+dp[i+1];
                //第二种情况，把第i个人和第i+1个人运过去
                if(i+1<=n) 
                    dp[i]=min(dp[i],a[3]+a[2]+a[i+1]+a[3]+dp[i+2]);
                //第三种情况，把第i、i+1、i+2个人运过去
                if(i+2<=n) 
                    dp[i]=min(dp[i],a[3]+a[2]+a[4]+a[2]+a[i+2]+a[4]+dp[i+3]);
            }
            cout<<dp[4]+a[3]<<endl;

        }
    }
    return 0;
}