给定一个长度为 $n$ 的仅包含小写字母的字符串。 $S[l : r]$ 表示从第 $l$ 个字符到第 $r$ 个字符连接而成的子串。 $B$ 是一个布尔表达式，艾弗森括号定义为： $$[B]= \begin{cases} 1, & \text{如果 } B \text{ 为真} \\ 0, & \text{其他情况} \end{cases}$$ $\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数。 我们定义 $f(i) = \sum_{j=1}^{i-1} [S[1 : j] == S[i - j + 1 : i]] \times \gcd(i, j)$。 现在要求 $\prod_{i=1}^{n} (f(i) + 1) \pmod{998\,244\,353}$ 的值。

输入格式

第一行输入一个正整数 $T(T \le 10)$，表示测试用例的数量。 对于每个测试用例，输入一个长度不超过 $10^6$ 的小写字母字符串 $S$。

输出格式

对于每个测试用例，输出一行包含一个正整数，表示答案。

样例

样例输入 1

5
aaaaa
aabaab
abcdefghi
abaabaaba
abbabbabb

样例输出 1

150
48
1
3840
1344