#include <iostream>
#include <vector>
using namespace std;
int f(const vector<int> &v, vector<vector<int>> &dp, int i, int j){
	if(dp[i][j]!=-1)	return dp[i][j];
	int l = 1;
	int r = 1;
	if(i)	l = v[i-1];
	if(j<v.size())	r = v[j];
	int ans = 0;	// ans = 0 when i==j
	for(int k=i; k<j; k++){
		int x = f(v,dp,i,k) + l*v[k]*r + f(v,dp,k+1,j);
		if(ans<x)	ans = x;
	}
	return dp[i][j] = ans;
}
int f(const vector<int> &v){
	int n = v.size();
	vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
	return f(v,dp,0,n);
}
int main() {
	int t,n,x;
	vector<int> v;
	cin>>t;
	while(t--){
		cin>>n;
		v.clear();
		while(n--&&cin>>x)	v.push_back(x);
		cout<<f(v)<<endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgZihjb25zdCB2ZWN0b3I8aW50PiAmdiwgdmVjdG9yPHZlY3RvcjxpbnQ+PiAmZHAsIGludCBpLCBpbnQgail7CglpZihkcFtpXVtqXSE9LTEpCXJldHVybiBkcFtpXVtqXTsKCWludCBsID0gMTsKCWludCByID0gMTsKCWlmKGkpCWwgPSB2W2ktMV07CglpZihqPHYuc2l6ZSgpKQlyID0gdltqXTsKCWludCBhbnMgPSAwOwkvLyBhbnMgPSAwIHdoZW4gaT09agoJZm9yKGludCBrPWk7IGs8ajsgaysrKXsKCQlpbnQgeCA9IGYodixkcCxpLGspICsgbCp2W2tdKnIgKyBmKHYsZHAsaysxLGopOwoJCWlmKGFuczx4KQlhbnMgPSB4OwoJfQoJcmV0dXJuIGRwW2ldW2pdID0gYW5zOwp9CmludCBmKGNvbnN0IHZlY3RvcjxpbnQ+ICZ2KXsKCWludCBuID0gdi5zaXplKCk7Cgl2ZWN0b3I8dmVjdG9yPGludD4+IGRwKG4rMSx2ZWN0b3I8aW50PihuKzEsLTEpKTsKCXJldHVybiBmKHYsZHAsMCxuKTsKfQppbnQgbWFpbigpIHsKCWludCB0LG4seDsKCXZlY3RvcjxpbnQ+IHY7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWNpbj4+bjsKCQl2LmNsZWFyKCk7CgkJd2hpbGUobi0tJiZjaW4+PngpCXYucHVzaF9iYWNrKHgpOwoJCWNvdXQ8PGYodik8PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==

MgoyIDUgMTAKNSAxIDIgMyA0IDU=

2
2 5 10
5 1 2 3 4 5