#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
	template<typename T> inline void read(T &x){
		bool f=1;x=0;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
		x=f?x:-x;
	}
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
	   	if(x>9) write(x/10);
	   	putchar(('0'+x%10));
	}
	template <typename T,typename ...Args> inline void read(T &x,Args &...args){read(x);read(args...);}
	template<typename T> inline void write(T x,char c){write(x),putchar(c);}
}
using namespace IO;
const int mod=998244353;
int n,L,len[1000005],sum[5][2000050];
char s[1000005],str[1000005];
void init(){
	memset(sum,0,sizeof(sum));
	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,id;
	for(int i=1;i<L;i++){
		if(mx>i)len[i]=min(len[2*id-i],mx-i);
		else len[i]=1;
		while(str[i+len[i]]==str[i-len[i]])len[i]++;  
		if(len[i]+i>mx)mx=len[i]+i,id=i;
	}
}
void add(int op,int l,int r,int num){
	if(l>r)return ;
	sum[op][l]+=num;
	sum[op][l]%=mod;
	sum[op][r+1]-=num;
	sum[op][r+1]%=mod;
}
signed main(){
	int T;
	read(T);
	while(T--){
		cin>>s;
		init();
		manacher();
		for(int i=L-1;i>=1;--i)add(1,i-len[i]+1,i,i),add(2,i-len[i]+1,i,1);
		for(int i=1;i<L;i++)add(3,i,i+len[i]-1,i),add(4,i,i+len[i]-1,1);
		for(int i=1;i<L;i++){
			for(int j=1;j<=4;j++){
				sum[j][i]+=sum[j][i-1];
				sum[j][i]=(mod+sum[j][i])%mod;
			}
		}
		int ans=0;
		for(int i=2;i<L-2;i+=2){
			int A,B;
			A=((sum[1][i+2]-sum[2][i+2]*((i+2)/2))%mod+mod)%mod;
			B=((sum[3][i]-sum[4][i]*(i/2))%mod+mod)%mod;
			ans+=(A*B)%mod,ans%=mod;
		}
		write(ans,'\n');
	}
	return 0;
}