#pragma GCC optimize("O3", "unroll-loops")
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<climits>
#include<numeric>
using namespace std;
#define fastio() ios::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define int long long
#define SZ(x) (int)x.size()
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define trav(a) for(auto p:a)cout<<p<<" ";cout<<"\n";
const int MOD = 998244353;
const long long INF = 1e18 + 42;
//••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
/*Theorems reminder:
Wilson : (p-1)! mod p = -1 or p-1, p is prime
Fermet : a^-1 mod p = a^(p-2) mod p, p is prime,a^(p-1) = 1 mod p
exteuclid, modInverse, matrixExp., sieve
*/
inline void read (int*a, int n) {
      for (int i = 0; i < n; i++) cin >> a[i];
}
inline void read (vector<int>&a) {
      for (auto &x : a) cin >> x;
}
inline int add (int a, int b, int mod = MOD) {
      a += b; return a >= mod ? a - mod : a;
}
inline int sub (int a, int b, int mod = MOD) {
      a -= b; return a < 0 ? a + mod : a;
}
inline int mul (int a, int b, int mod = MOD) {
      return (int) ( (long long) ((a % mod) * (b % mod)) % mod);
}
inline int mpow (long long base, long long ex, int mod = MOD) {
      int res = 1;
      for (; ex > 0; ex >>= 1) {
            if (ex & 1) res = mul (res, base, mod);
            base = mul (base, base, mod);
      }
      return res;
}
inline int inv (int a, int mod = MOD) {
      return mpow (a, mod - 2, mod);
}
inline int __ceil (int n, int d) {
      return (n + d - 1) / d;
}
//••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••




int dp[1000001][2][2];
int getAns(int i, string &s, int n, int f, int r) {
      if (i >= (n + 1) / 2) {
            return f == 1 || r == 1;
      }


      if (dp[i][f][r] != -1)return dp[i][f][r];

      int ans = 0;
      if (f) {
            if (n % 2 == 1)
                  ans = mpow(26LL, n / 2 - i + 1) % MOD;
            else {
                  ans = mpow(26LL, n / 2 - i) % MOD;
            }
      }
      else {
            for (char c = 'A'; c <= s[i]; c++) {
                  if (c < s[i]) {
                        ans = add(ans, getAns(i + 1, s, n, 1, r) % MOD);
                  }
                  else {
                        if (s[n - i - 1] < s[i]) {
                              ans = add(ans, getAns(i + 1, s, n, f, 0) % MOD);
                        }
                        else
                              ans = add(ans, getAns(i + 1, s, n, f, r | (s[i] < (s[n - i - 1]))) % MOD);
                  }

            }
      }
      return dp[i][f][r] = ans;
}
bool isPal(string &s) {
      for (int i = 0; i < SZ(s) / 2; i++) {
            if (s[i] != s[SZ(s) - i - 1])return false;
      }
      return true;
}
void SolveCase() {



      int n;
      cin >> n;
      string s;
      cin >> s;

      int f = 0;
      if (isPal(s))f = 1;
      for (int i = 0; i <= n; i++) {
            dp[i][0][0] = dp[i][1][0] = -1;
            dp[i][0][1] = dp[i][1][1] = -1;
      }

      cout << getAns(0, s, n, 0, 0) + f << "\n";
}
signed main()
{
      fastio()
      int tt = 1; cin >> tt;
      for (int t = 1; t <= tt; t++) {
            // cout << "Case #" << t << ": ";
            SolveCase();
      }
      // cerr << "Time : " << 1000 * ( (double) clock() ) / (double) CLOCKS_PER_SEC << "ms\n";
}