#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000 + 5;
const int B = 31, P = 998244353;

int T, N;
char s[MAX_N];
int h1[MAX_N], h2[MAX_N], pw[MAX_N];
int sl[MAX_N], sr[MAX_N];


int main() {
    scanf("%d", &T);
    for (int tid = 1; tid <= T; tid ++) {
        scanf("%s", s + 1);
        N = strlen(s + 1);
        h1[0] = h2[N + 1] = 0, pw[0] = -1;
        for (int i = 1; i <= N; i ++) {
            pw[i] = pw[i - 1] * B;
            sl[i] = sr[i] = 0;
        }
        for (int i = 1; i <= N; i ++) {
            h1[i] = h1[i - 1] * B + (s[i] - 'a' + 1);
        }
        for (int i = N; i >= 1; i --) {
            h2[i] = h2[i + 1] * B + (s[i] - 'a' + 1);
        }
        for (int i = 1; i <= N; i ++) {
            for (int j = i; j <= N; j ++) {
                int t1 = h1[j] + h1[i - 1] * pw[j - i + 1];
                int t2 = h2[i] + h2[j + 1] * pw[j - i + 1];
                if (t1 == t2) {
                    sr[i] += j;
                    sr[i] -= sr[i] >= P ? P : 0;
                    sl[j] += i;
                    sl[j] -= sl[j] >= P ? P : 0;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < N; i ++) {
            ans = (ans + 1ll * sl[i] * sr[i + 1]) % P;
        }
        printf("%d\n", ans);
    }
    return 0;
}