#include <bits/stdc++.h>
using namespace std;
#define file(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
typedef long long ll;
const int N = 2e6 + 5, mod = 998244353;
int n, mxr, mid, l, ans, L, R;
int len[N], p[N], s[N], c1[N], c2[N];
char a[N], c[N];
void init()
{
	for (int i = 1; i <= l; i++)
	{
		L = (i + 1) / 2, R = L + (len[i] / 2);
		c1[L] = (c1[L] + i) % mod, c1[R] = (c1[R] - i + mod) % mod;
		c2[L] = (c2[L] + 1) % mod, c2[R] = (c2[R] - 1 + mod) % mod;
	}
	for (int i = 1; i <= n; i++)
	{
		c1[i] = (c1[i - 1] + c1[i]) % mod;
		c2[i] = (c2[i - 1] + c2[i]) % mod;
		p[i] = (c1[i] - (ll)c2[i] * i % mod + mod) % mod;
	}
	for (int i = 1; i <= n + 1; i++)
		c1[i] = c2[i] = 0;
	for (int i = 1; i <= l; i++)
	{
		R = i / 2 + 1, L = R - (len[i] / 2);
		c1[L] = (c1[L] + i) % mod, c1[R] = (c1[R] - i + mod) % mod;
		c2[L] = (c2[L] + 1) % mod, c2[R] = (c2[R] - 1 + mod) % mod;
	}
	for (int i = 1; i <= n; i++)
	{
		c1[i] = (c1[i - 1] + c1[i]) % mod;
		c2[i] = (c2[i - 1] + c2[i]) % mod;
		s[i] = (c1[i] - (ll)c2[i] * i % mod + mod) % mod;
	}
	for (int i = 1; i <= n + 1; i++)
		c1[i] = c2[i] = 0;
}
void manacher()
{
	l = mxr = mid = 0;
	c[++l] = '#';
	for (int i = 1; i <= n; i++)
		c[++l] = a[i], c[++l] = '#';
	c[0] = '&', c[l + 1] = '|';
	for (int i = 1; i <= l; i++)
	{
		if (i <= mxr)
			len[i] = min(len[(mid << 1) - i], mxr - i + 1);
		else
			len[i] = 1;
		while (c[i + len[i]] == c[i - len[i]])
			len[i]++;
		if (i + len[i] - 1 >= mxr)
			mxr = i + len[i] - 1, mid = i;
	}
}
signed main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", a + 1), n = strlen(a + 1);
		manacher(), init();
		ans = 0;
		for (int i = 1; i < n; i++)
			ans = (ans + (ll)p[i] * s[i + 1]) % mod;
		printf("%d\n", ans);
	}
	return 0;
}