#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e3 + 100, mod = 998244353;

typedef long long ll;

ll T, n;
ll a[N], f[2][N][N];

ll quick_pow (ll x, ll k) {
    if (k == 0) return 0;
    ll res = 1;
    while (k) {
        if (k & 1) res = (res * x) % mod;
        k >>= 1; x = (x * x) % mod;
    }
    return res;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while (T -- ) {
        memset (f, 0, sizeof f);
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int len = 2; len <= n; len ++ )
            for (int l = 1; l <= n - len + 1; l ++ ) {
                int r = l + len - 1;
                f[0][l][r] = max(f[0][l + 1][r] + quick_pow(a[l], a[l + 1]), f[1][l + 1][r] + quick_pow(a[l], a[r]));
                f[1][l][r] = max(f[0][l][r - 1] + quick_pow(a[r], a[l]), f[1][l][r - 1] + quick_pow(a[r], a[r - 1]));
            }
        cout << max(f[0][1][n], f[1][1][n]) << '\n';
    }
    return 0;
}

WA在了#8