回文串

小 F 有一个长度为 $n$ 的字符串 $S$，你需要帮他算一算有多少个字符串 $T$ 满足如下条件：

• $T$ 是一个回文串。
• $T$ 的长度不超过 $n$。
• $T$ 的字典序小于等于 $S$。

答案可能很大，你只需输出答案对 $998244353$ 取模后的结果即可。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个字符串 $S$。

输出格式

输出 $T$ 行，第 $j$ 行表示第 $j$ 组数据的答案对 $998244353$ 取模后的结果。

提示

本题共 $20$ 组数据。

数据随机：每个字符在 $[a,z]$ 内等概率随机生成。

对于全部的数据，$1\leq T\leq 10^7$，$1\leq \sum |S|\leq 10^7$，且 $S$ 仅由小写字母组成。