#include <iostream>
#include <cstdio>
#include <algorithm>
#define mod 998244353
using namespace std;
long long int dp[3003][3003][2],a[1003];
long long int mi(long long int x,long long int y){
    long long int sum=1;
    if(y==0&&x==0)
        return 0;
    while(y){
        if(y&1)sum=sum*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return sum;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        long long int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)  
            scanf("%lld",&a[i]);
            for(int i=1;i<=n+2;i++)
                for(int j=i;j<=n+2;j++)
                    dp[i][j][0]=dp[i][j][1]=0;
            dp[1][n-1][1]=n;
            dp[2][n][1]=1;
            dp[3][n+1][1]=0;
            a[n+1]=0;
           for(int j=n-2;j>0;j--)
                for(int l=1,r=j;r<=n;r++,l++){
                    if(dp[l][r+1][0]+mi(a[dp[l][r+1][1]],a[r+1])<dp[l-1][r][0]+mi(a[dp[l-1][r][1]],a[l-1])){
                        if(l-1>0)
                            dp[l][r][0]=dp[l-1][r][0]+mi(a[dp[l-1][r][1]],a[l-1]);
                        dp[l][r][1]=l-1;
                    }
                    else
                        if(dp[l][r+1][0]+mi(a[dp[l][r+1][1]],a[r+1])==dp[l-1][r][0]+mi(a[dp[l-1][r][1]],a[l-1]))
                            if(a[dp[l][r+1][1]]>a[dp[l-1][r][1]])
                            {
                                if(r+1<=n)
                                    dp[l][r][0]=dp[l][r+1][0]+mi(a[dp[l][r+1][1]],a[r+1]);
                                dp[l][r][1]=r+1;
                            }
                            else{
                                if(l-1>0)
                                    dp[l][r][0]=dp[l-1][r][0]+mi(a[dp[l-1][r][1]],a[l-1]);
                                 dp[l][r][1]=l-1;
                            }
                        else{
                            if(r+1<=n)
                                    dp[l][r][0]=dp[l][r+1][0]+mi(a[dp[l][r+1][1]],a[r+1]);
                                dp[l][r][1]=r+1;
                        }
                        
                }
        for(int i=1;i<=n;i++)
            ans=max(ans,dp[i][i][0]+mi(a[dp[i][i][1]],a[i]));
        printf("%lld\n",ans);
    }
    return 0;
}