#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;

signed main() {

    if(fopen("yl.in", "r")) {
        freopen("yl.in", "r", stdin);
        freopen("yl.out", "w", stdout);
    }

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        vector<int> vec(n);
        rep(i,0,n - 1) cin >> vec[i];
        sort(vec.begin(), vec.end());
        deque<int> d1;
        long long ans = 0;
        int side = 1;
        for(auto it = vec.begin(); it != vec.end(); ++ it) {
            if(side) {
                if(d1.size()) ans += 1ll * d1.front() * (*it);
                d1.push_front(*it);
            } else {
                if(d1.size()) ans += 1ll * d1.back() * (*it);
                d1.push_back(*it);
            }
            side ^= 1;
        }
        cout << ans + 1ll * d1.front() * d1.back() << endl;
    }
    //     side = 1;
    //     for(auto it = vec.rbegin(); it != vec.rend() && *it > 0; ++ it) {
    //         if(side) {
    //             if(d2.size()) ans += 1ll * d2.front() * (*it);
    //             d2.push_front(*it);
    //         } else {
    //             if(d2.size()) ans += 1ll * d2.back() * (*it);
    //             d2.push_back(*it);
    //         }
    //         side ^= 1;
    //     }

    //     if(d1.size() == 0) ans += d2.front() * d2.back();
    //     else if(d2.size() == 0) ans += d1.front() * d1.back();
    //     else {
    //         ans += min(1ll * d1.front() * d2.front() + 1ll * d1.back() * d2.back(), 1ll * d1.back() * d2.front() + 1ll * d1.front() * d2.back());
    //     }
    //     cout << ans << endl;
    // }
    return 0;
}