文件目录

#include <bits/stdc++.h>
using namespace std;
int t, n, a[10005];
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        int ans = 0;
        while (n > 3)
        {
            int p1 = 2 * a[2];
            int p2 = a[1] + a[n - 1];
            ans += min(p1, p2) + a[1] + a[n]; // 用最快方案，送走两个最重的
            n -= 2;
        }
        if (n == 3)
            ans += a[1] + a[2] + a[3];
        else if (n == 2)
            ans += a[2];
        else
            ans += a[1];
        cout << ans << endl;
    }
    return 0;
}