//
//  na 2411.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/13.
//

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long int ll;
const int maxn = 1e6 + 5, mod = 998244353;
int t, n, m, d[maxn * 2];
char s[maxn * 2];
int lbs[maxn], lss[maxn], rbs[maxn], rss[maxn], ls[maxn], rs[maxn];
// seq[i] = -i
inline void add(int &a, int b){
    if((a += b) >= mod)
        a -= mod;
}
inline void mnu(int &a, int b){
    if((a -= b) < 0)
        a += mod;
}
inline int mul(int a, int b){
    return ll(a) * b % mod;
}
inline void clear_ss(){
    for(int i = 1; i <= n; ++i)
        lbs[i] = lss[i] = rbs[i] = rss[i] = 0;
}
inline void pseq(int *seq){
    for(int i = 1; i <= n; ++i)
        cerr << seq[i] << ' ';
}
inline void calc_sum(){
    for(int i = 2; i <= n; ++i){
        add(lss[i], lss[i - 1]);
        add(lbs[i], lbs[i - 1]);
        add(rss[i], rss[i - 1]);
        add(rbs[i], rbs[i - 1]);
    }
//    cerr << "l seq sum: ";
//    pseq(lss);
//    cerr << endl << "l base sum: ";
//    pseq(lbs);
//    cerr << endl << "r seq sum: ";
//    pseq(rss);
//    cerr << endl << "r base sum: ";
//    pseq(rbs);
//    cerr << endl;
    for(int i = 1; i <= n; ++i){
        ls[i] = mul(mod - i, lss[i]);
        add(ls[i], lbs[i]);
        rs[i] = mul(mod - i, rss[i]);
        add(rs[i], rbs[i]);
    }
//    cerr << "ls: ";
//    pseq(ls);
//    cerr << endl << "rs: ";
//    pseq(rs);
//    cerr << endl;
}
inline void add_laz(int lt, int rt){
    if(lt > rt)
        return;
//    cerr << "*************  add_laz: " << lt << " <-> " << rt << endl;
    int mid = (lt + rt) >> 1;
    if((rt - lt) & 1){ // even
        ++mid;
        add(lss[lt], 1);
        add(lbs[lt], lt + rt);
        mnu(lss[mid], 1);
        mnu(lbs[mid], lt + rt);
        add(rss[mid], 1);
        add(rbs[mid], mid + mid - 1);
        mnu(rss[rt + 1], 1);
        mnu(rbs[rt + 1], mid + mid - 1);
    }else{ // odd
        add(lss[lt], 1);
        add(lbs[lt], lt + rt);
        mnu(lss[mid + 1], 1);
        mnu(lbs[mid + 1], lt + rt);
        add(rss[mid], 1);
        add(rbs[mid], mid + mid);
        mnu(rss[rt + 1], 1);
        mnu(rbs[rt + 1], mid + mid);
    }
//    calc_sum();
//    clear_ss();
}
inline void solve(){
    cin >> s;
    n = 0;
    while(s[++n]);
    clear_ss();
    for(int i = n - 1; i >= 0; --i)
        s[i << 1 | 1] = s[i];
    for(int i = 1; i < n; ++i)
        s[i << 1] = '#';
    m = n * 2;
    s[0] = s[m] = '#';
//    for(int i = 0; i <= m; ++i)
//        cerr << s[i];
//    cerr << endl;
    int l = -1, r = -1, k, p, rd;
    for(int i = 0; i <= m; ++i){
        k = i > r? 1: min(d[l + r - i], r - i + 1);
        while(i - k >= 0 && i + k <= m && s[i - k] == s[i + k])
            ++k;
        d[i] = k;
        p = (i + 1) >> 1;
        rd = k >> 1;
        if(i & 1){ // isalpha(s[i])
            add_laz(p - rd + 1, p + rd - 1);
        }else{ // s[i] = '#'
            add_laz(p - rd + 1, p + rd);
        }
        --k;
        if(i + k > r){
            r = i + k;
            l = i - k;
        }
    }
    calc_sum();
    int ans = 0;
    for(int m = 1; m < n; ++m)
        add(ans, mul(rs[m], ls[m + 1]));
    cout << ans << endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> t;
    while(t--)
        solve();
    return 0;
}