#include<bits/stdc++.h>
using namespace std;
long long l[1001];
const int MOD=998244353;
long long dp[1001][1001][2];
long long qpow(long long x,long long y) { //quick pow
	if(x==0 and y==0) return 0;
	if(y == 1) {
		return x;
	}
	long long p = qpow(x,y / 2);
	p *= p;
	p %= MOD;
	if(y % 2 == 1) {
		p *= x;
		p %= MOD;
	}
	return p;
}
int main() {
	int t;
	cin>>t;
	int len;
	for(int k=0; k<t; k++) {
		cin>>len;
		for(int i=1; i<=len; i++) {
			cin>>l[i];
		}
		memset(dp,0,sizeof(0));
		for(int n=len; n>=1; n--) {
			for(int i=1; i<=len-n+1; i++) { //start point
				int j=i+n-1;//till point
				dp[i][j][0]=max(dp[i-1][j][0]+qpow(l[i-1],l[i]),dp[i][j+1][1]+qpow(l[j+1],l[i]));
				dp[i][j][1]=max(dp[i-1][j][0]+qpow(l[i-1],l[j]),dp[i][j+1][1]+qpow(l[j+1],l[j]));
			}
		}
		long long ans=0;
		for(int i=1; i<=len; i++) {
			ans=max(ans,max(dp[i][i][0],dp[i][i][1]));
		}
		cout<<ans<<'\n';
	}
	return 0;
}

MLE on #8 悬2关