#include <bits/stdc++.h>
#define int long long
using namespace std;
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXC = 26;
const int mod = 998244353;
int T;
int nm[MAXN][2];
char str[MAXN];
class PAM {
	public:
		struct node {
			map<int, int> ch;
			int fail, len, num;
			int sum;
		} T[MAXN];
		int las, tot;
		inline int get_fail(int x, int pos) {
			while (str[pos - T[x].len - 1] != str[pos]) {
				x = T[x].fail;
			}
			return x;
		}
		void init() {
			T[0].ch.clear(), T[1].ch.clear();
			T[0].fail = 1, T[1].fail = 0;
			T[0].len = 0, T[1].len = -1;
			T[0].num = T[1].num = T[0].sum = T[1].sum = 0;
			las = 0, tot = 1;
		}
		void insert1(char s[], int len) {
			s[0] = -1;
			for (int i = 1; i <= len; i++) {
				int p = get_fail(las, i);
				if (!T[p].ch[s[i] - 'a']) {
					T[++tot].len = T[p].len + 2;
					T[tot].ch.clear();
					int u = get_fail(T[p].fail, i);
					T[tot].fail = T[u].ch[s[i] - 'a'];
					T[tot].num = T[T[tot].fail].num + 1;
					T[tot].sum = (T[T[tot].fail].sum + T[tot].len) % mod;
					T[p].ch[s[i] - 'a'] = tot;
				}
				las = T[p].ch[s[i] - 'a'];
				nm[i][0] = (1ll * T[las].num * (i + 1) % mod - T[las].sum + mod) % mod;
			}
		}
		void insert2(char s[], int len) {
			s[0] = 0;
			for (int i = 1; i <= len; i++) {
				int p = get_fail(las, i);
				if (!T[p].ch[s[i] - 'a']) {
					T[++tot].len = T[p].len + 2;
					T[tot].ch.clear();
					int u = get_fail(T[p].fail, i);
					T[tot].fail = T[u].ch[s[i] - 'a'];
					T[tot].num = T[T[tot].fail].num + 1;
					T[tot].sum = (T[T[tot].fail].sum + T[tot].len) % mod;
					T[p].ch[s[i] - 'a'] = tot;
				}
				las = T[p].ch[s[i] - 'a'];
				int pos = len - i + 1;
				nm[pos][1] = (1ll * T[las].num * (pos - 1) % mod + T[las].sum) % mod;
			}
		}
} tree;
signed main() {
//	cin.tie(nullptr)->ios::sync_with_stdio(false);
	cin >> T;
	while (T--) {
		cin >> str + 1;
		int n = strlen(str + 1);
		tree.init();
		tree.insert1(str, n);
		int n2 = n >> 1;
		for (int i = 1; i <= n2; i++) swap(str[i], str[n - i + 1]);
		tree.init();
		tree.insert2(str, n);
		int res = 0;
		for (int i = 1; i < n; i++)
			res = (res + 1ll * nm[i][0] * nm[i + 1][1] % mod) % mod;
		cout << res << endl;
		for(int i=1;i<=n;i++) str[i]='\0';
	}
}