rt.样例都对了qwq

#include<bits/stdc++.h>
#define p 998244353
using namespace std;
typedef long long ll;
int t,n,a[1005];
ll dp[1005][1005][2];
inline ll pow_mod(int a,int b){
	if(a==0&&b==0)return 0;
	ll res=1;
	while(b){
		if(b&1)res=res*a%p;
		a=a*a%p;b>>=1; 
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	for(;t--;){
		cin>>n;
		for(int i=1;i<=n;++i)cin>>a[i];
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				dp[i][j][0]=dp[i][j][1]=0;
		for(int len=2;len<=n;++len)
			for(int i=1,j=i+len-1;j<=n;++i,++j){
				dp[i][j][0]=max(dp[i+1][j][0]+pow_mod(a[i],a[i+1]),dp[i+1][j][1]+pow_mod(a[i],a[j]));
				dp[i][j][1]=max(dp[i][j-1][0]+pow_mod(a[j],a[i]),dp[i][j-1][1]+pow_mod(a[j],a[j-1]));
			}
		cout<<max(dp[1][n][0],dp[1][n][1])<<"\n";
	}
	return 0;
}