#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 998244353;
int t, n, maxl[1000010];
long long ld[1000010], ldd[1000010];
long long rd[1000010], rdd[1000010];
char s[1000010], ns[2000010];
void manachar() {
    maxl[1] = 0;
    int maxr = 0, maxi = 0;
    for (int i = 1; i <= 2 * n - 1; i++) {
        if (maxr > i) {
            maxl[i] = min(maxl[2 * maxi - i], maxr - i);
        } else {
            maxl[i] = 0;
        }
        while (ns[i - maxl[i] - 1] == ns[i + maxl[i] + 1]) {
            maxl[i]++;
        }
        if (i + maxl[i] > maxr) {
            maxr = i + maxl[i];
            maxi = i;
        }
    }
}
void addl(int l, int r, int first) {
    // printf("%d ~ %d add l %d down\n", l, r, first);
    ld[l] += first;
    ld[r + 1] -= first;
    ldd[l + 1]--;
    ldd[r + 1]++;
    ld[r + 1] += r - l;
}
void addr(int l, int r, int first) {
    // printf("%d ~ %d add r %d down\n", l, r, first);
    rd[l] += first;
    rd[r + 1] -= first;
    rdd[l + 1]--;
    rdd[r + 1]++;
    rd[r + 1] += r - l;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        ns[0] = '?';
        for (int i = 1; i <= n; i++) {
            ld[i] = ldd[i] = rd[i] = rdd[i] = 0;
            ns[2 * i - 1] = s[i];
            ns[2 * i] = '#';
        }
        ns[2 * n] = '$';
        manachar();
        for (int pos = 1; pos <= 2 * n - 1; pos++) {
            if (pos % 2 == 1) {
                int i = (pos + 1) / 2;
                int l = maxl[pos] / 2;
                // printf("%d : %d %d\n", pos, i, l);
                addl(i, i + l, i);
                addr(i - l, i, i + l);
            } else {
                int i1 = pos / 2;
                int i2 = i1 + 1;
                int l = (maxl[pos] + 1) / 2;
                // printf("%d : %d %d %d\n", pos, i1, i2, l);
                addl(i2, i2 + l - 1, i1);
                addr(i1 - l + 1, i1, i2 + l - 1);
            }
            for (int i = 1; i <= n; i++) {
                // printf("r %d : %d %d\n", i, rd[i], rdd[i]);
            }
        }
        // for (int i = 1; i <= n; i++) {
        //     printf("r %d : %d %d\n", i, rd[i], rdd[i]);
        // }
        for (int i = 1; i <= n; i++) {
            ldd[i] += ldd[i - 1];
            rdd[i] += rdd[i - 1];
            ldd[i] %= mod;
            rdd[i] %= mod;
        }
        for (int i = 1; i <= n; i++) {
            ld[i] += ldd[i];
            rd[i] += rdd[i];
            ld[i] += ld[i - 1];
            rd[i] += rd[i - 1];
            ld[i] %= mod;
            rd[i] %= mod;
            // printf("%d : %lld %lld\n", i, ld[i], rd[i]);
        }
        long long ans = 0;
        for (int i = 1; i < n; i++) {
            ans += ld[i] * rd[i + 1] % mod;
        }
        printf("%lld\n", ans % mod);
    }
    return 0;
}