#include<cstdio>
#include<cmath>
#include <cstring>

#define ll long long
using namespace std;

inline int in() {
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')ch = getchar();
    while (ch >= '0' && ch <= '9') {
        (x *= 10) += ch - '0';
        ch = getchar();
    }
    return x;
}

const int mod = 998244353;

int lowbit(int x) {
    return x & 1;
}

int Pow(int x, int y) {
    if (!x)return x;
    int result = 1;
    x %= mod;
    while (y) {
        if (lowbit(y))result *= x;
        y >>= 1;
        x *= x;
        x %= mod;
        result %= mod;
    }
    return result;
}

int num[1007] = {0};
ll dp[1007][1007][2] = {0};

int main() {
    int T = in();
    while (T--) {
        int n = in();
        memset(num, 0, sizeof(num));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)num[i] = in();
        for (int i = 1; i <= n; i++) { //只从左边取值
            dp[i][n + 1][0] = dp[i - 1][n + 1][0] + Pow(num[i - 1], num[i]);
        }
        for (int i = n; i >= 1; i--) {
            dp[0][i][1] = dp[0][i + 1][1] + Pow(num[i + 1], num[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = n; j > i; j--) {
                dp[i][j][0] = max(dp[i - 1][j][0] + Pow(num[i - 1], num[i]), dp[i - 1][j][1] + Pow(num[j], num[i]));
                dp[i][j][1] = max(dp[i][j + 1][0] + Pow(num[i], num[j]), dp[i][j + 1][1] + Pow(num[j + 1], num[j]));
            }
        }
        ll ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = max(ans, dp[i][i + 1][1]);
            ans = max(ans, dp[i][i + 1][0]);
        }
        printf("%lld\n", ans);
    }

}```