#include #include #include

using namespace std;

int minCrossingTime(vector& times) { sort(times.begin(), times.end()); int n = times.size(); int total_time = 0;

while (n > 3) {
    // Compare two strategies for transporting the two slowest people
    int strategy1 = times[1] + times[0] + times[n-1] + times[1];
    int strategy2 = times[n-1] + times[0] + times[n-2] + times[0];
    total_time += min(strategy1, strategy2);
    n -= 2; // Two slowest people have been transported
}

// Handle the base cases
if (n == 1) {
    total_time += times[0];
} else if (n == 2) {
    total_time += times[1];
} else if (n == 3) {
    total_time += times[0] + times[1] + times[2];
}

return total_time;

}

int main() { int t; cin >> t;

while (t--) {
    int n;
    cin >> n;
    vector<int> times(n);
    for (int i = 0; i < n; ++i) {
        cin >> times[i];
    }
    cout << minCrossingTime(times) << endl;
}

return 0;

}