#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int T,n; int a[1010]; int sum; int min(int a,int b) { return a>b?b:a; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); CL(a, 0); for(int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1, a+n+1); sum=0; while(n) { if(n == 1) { sum+=a[1]; break; } else if(n==2) { sum+=a[2]; break; } else if(n==3) { sum+=a[3]+a[1]+a[2]; break; } else { sum+=min(a[2]*2+a[1]+a[n],a[1]*2+a[n]+a[n-1]); n-=2; } } printf("%d\n",sum); } return 0; }