#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, d2;
        int side = 1;
        long long ans = 0;
        for(auto it = vec.begin(); it != vec.end() && *it <= 0; ++ 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;
        }
        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;
}