// . . . Bismillahir Rahmanir Rahim . . .
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg_out cout
#define debug(...) dbg_out << "DBG )> "; __f(#__VA_ARGS__, __VA_ARGS__);
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> pr) { out << "{ " << pr.first << ", " << pr.second << " }"; return out; }
template<typename T1> ostream& operator<<(ostream& out, vector<T1> vec) { out << "{ "; for (auto &x: vec) out << x << ", "; out << "}"; return out; }
template<typename T1, size_t size> ostream& operator<<(ostream& out, array<T1, size> arr) { out << "{ "; for (auto &x: arr) out << x << ", "; out << "}"; return out; }
template<typename T1, typename T2> ostream& operator<<(ostream& out, map<T1, T2> mp) { out << "{ ";for (auto &x: mp) out << x.first << ": " << x.second <<  ", "; out << "}"; return out; }
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { while (isspace(name[0])) name++; (isalpha(name[0]) || name[0] == '_') ? dbg_out << name << ": " << arg1 << "\n" : dbg_out << arg1 << "\n"; dbg_out.flush();}
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) { const char *comma = strchr(names + 1, ','); while (isspace(names[0])) names++; (isalpha(names[0]) || names[0] == '_') ? dbg_out.write(names, comma - names) << ": " << arg1 << " | " : dbg_out << arg1 << " | "; __f(comma + 1, args...);}
#else
#define debug(...)
#endif
 
ll gcd(ll a, ll b){ while (b){ a %= b; swap(a, b);} return a;}
ll lcm(ll a, ll b){ return (a/gcd(a, b)*b);}
ll ncr(ll a, ll b){ ll x = max(a-b, b), ans=1; for(ll K=a, L=1; K>=x+1; K--, L++){ ans = ans * K; ans /= L;} return ans;}
ll bigmod(ll a,ll b,ll mod){ if(b==0){ return 1;} ll tm=bigmod(a,b/2,mod); tm=(tm*tm)%mod; if(b%2==1) tm=(tm*a)%mod; return tm;}
ll egcd(ll a,ll b,ll &x,ll &y){ if(a==0){ x=0; y=1; return b;} ll x1,y1; ll d=egcd(b%a,a,x1,y1); x=y1-(b/a)*x1; y=x1; return d;}
ll modpow(ll a,ll p,ll mod) {ll ans=1;while(p){if(p%2)ans=(ans*a)%mod;a=(a*a)%mod;p/=2;} return ans;}
ll inverse_mod(ll n,ll mod) {return modpow(n,mod-2,mod);}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		
		ll ara[n];
		for(int K = 0; K < n; K++) cin >> ara[K];
		sort(ara, ara+n);
		
		int i = 0, j = -1;
		for(int K = 0; K < n; K++){
			if(ara[K] >= 0) break;
			j = K;
		}
		
		if(j == n-1 || j == -1){
			if(j == n-1) reverse(ara, ara+n);
			
			ll cop[n];
			i = 0; j = n-1;
			for(int K = 0; K < n; K+=2){
				cop[i++] = ara[K];
				if(K+1 < n) cop[j--] = ara[K+1];
			}
			
			ll ans = 0;
			for(int K = 1; K < n; K++) ans += cop[K]*cop[K-1];
			ans += cop[0]*cop[n-1];
			
			cout << ans << "\n";
			
			continue;
		}
		
		
		reverse(ara, ara+j+1);
		
		//for(int K = 0; K < n; K++) cout << ara[K] << ' ';
		//cout << "\n";
			
		ll cop[n];
		//i = 0; j = n-1;
		int x = j;
		//cout << i << ' '<< j << ' ' << x << "\n";
		for(int K = 0; K <= x; K+=2){
			cop[i++] = ara[K];
			if(K+1 <= x) cop[j--] = ara[K+1];
		}
		ll ans = 0;
		for(int K = 1; K <= x; K++) ans += cop[K]*cop[K-1];
		//ans += cop[0]*cop[n-1];
		//for(int K = 0; K <= x; K++) cout <<  cop[K] << ' ';
		//cout<< ans << "\n";
		
		i = x+1; j = n-1; int y = n-1;
		//cout << i << ' ' << j << ' ' << x << ' ' << y << "\n"; 
		for(int K = i; K <= y; K+=2){
			cop[i++] = ara[K];
			if(K+1 <= y) cop[j--] = ara[K+1];
		}
		
		for(int K = x+2; K <= y; K++) ans += cop[K]*cop[K-1];
		
		
		//for(int K = x+1; K <= y; K++) cout <<  cop[K] << ' ';
		//cout<< ans << "\n";
		
		ans += max(cop[0]*cop[x+1] + cop[x]*cop[y], cop[0]*cop[y] + cop[x]*cop[x+1]);
		
		cout << ans << "\n";
		
		
		
		//int ans = 0;
		//if(i <= j){
			//ans += min(ara[i]*ara[min(n-1, j+1)]+ara[min(j, i+1)]*ara[min(n-1, j+2)], ara[i]*ara[min(n-1, j+2)]+ara[min(j, i+1)]*ara[min(n-1, j+1)]);
		//}
		
		//while(i <= j){
			//if(i+2 <= j){
				//ans += ara[i]*ara[i+2];
			//}
			//if(i+3 <= j){
				//ans += ara[i+1] * ara[i+3];
			//}
			
			//i += 2;
		//}
		
		//i = j+1; j = n-1;
		//while(i <= j){
			//if(i+2 <= j){
				//ans += ara[i]*ara[i+2];
			//}
			//if(i+3 <= j){
				//ans += ara[i+1] * ara[i+3];
			//}
			
			//i += 2;
		//}
		
		//cout << ans << "\n";
	}
	
	return 0;
}