#include <bits/stdc++.h>
#define int long long
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");
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

answer.code: In function 'void solve()':
answer.code:48:2: error: 'cin' was not declared in this scope
  cin>>s;\x0d
  ^
answer.code:48:2: note: suggested alternative:
In file included from /usr/include/x86_64-linux-gnu/c++/4.8/bits/stdc++.h:74:0,
                 from answer.code:1:
/usr/include/c++/4.8/iostream:60:18: note:   'std::cin'
   extern istream cin;  /// Linked to standard input
                  ^
answer.code:73:2: error: 'cout' was not declared in this scope
  cout << ans << '\n';\x0d
  ...