#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int T, n, a[2000], i, k;
cin >> T;
while(T--)
{
cin>>n;
for (i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
k = 0;
while(1)
{
if (n==1)
{
k+=a[0];
break;
}
if (n==2)
{
k+=a[1];
break;
}
if (n==3)
{
k+=a[0]+a[1]+a[2];
break;
}
k+=min(a[0]*2+a[n-1]+a[n-2],a[0]+a[1]*2+a[n-1]);
n-=2;
}
cout<<k<<endl;
}
return 0;
}