#include <bits/stdc++.h>
#define int long long
#define file(x) {freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define io Fastio::cin
#define IO Fastio::cout
int T = 1;
const int mod=998244353;
const int maxn=1e7;
char str[maxn];
int n,L;
int p[maxn];
char s[maxn];
int data[5][2000100];
void init(){
    memset(data,0,sizeof(data));
    n=strlen(s);
    str[0]='@';
    str[1]='#';
    for(int i=0;i<n;i++){
        str[i*2+2]=s[i];
        str[i*2+3]='#'; 
    }
    L=n*2+2; 
    str[L]=0; 
}
void manacher(){
    int mx=0;
    int id;
    for(int i=1;i<L;i++){
        if(mx>i){
            p[i]=std::min(p[2*id-i],mx-i);
        }
        else p[i]=1;
        while(str[i+p[i]]==str[i-p[i]])  
            p[i]++;  
            if(p[i]+i>mx){  
                mx=p[i]+i;  
                id=i;  
        	}  
    }
}
void add(int op,int l,int r,int num)
{
    if (l>r) return ;
    data[op][l] += num;
    data[op][l] %= mod;
    data[op][r+1] -= num;
    data[op][r+1] %= mod;
}
void solve(){
	cin>>s;
    init();
    manacher();
    for(int i=L-1;i>=1;--i) {
        add(1,i-p[i]+1,i,i); 
        add(2,i-p[i]+1,i,1); 
    }
    for (int i=1;i<L;i++)  {
        add(3,i,i+p[i]-1,i); 
        add(4,i,i+p[i]-1,1);
    }
    for (int i=1;i<L;i++){
        for (int j=1;j<=4;j++){
            data[j][i]+=data[j][i-1];
            data[j][i]=(mod+data[j][i])%mod;
        }
    }
    int ans=0;
    for (int i=2;i<L-2;i+=2){
        int aa,bb;
        aa=((data[1][i+2]-(long long)data[2][i+2]*((i+2)/2))%mod+mod)%mod;
        bb=((data[3][i]-(long long)data[4][i]*(i/2))%mod+mod)%mod;
        ans+=((long long)aa*(long long)bb)%mod;
        ans%=mod;
    }
    cout << ans << '\n';
}
int32_t main(){
//	file("A");
	Fastio::cin >> T;
	while(T--){
		solve();
	}
	return 0;
}