Problem Description

There is a string of length $n$ which only contains lowercase letters.

$S[l:r]$ represents the string concatenated from the $l$ -th character to the $r$ -th character.

$B$ is a boolean expression,the Iverson brackets

$$[B]=\left\\\{\begin{aligned}&1,if\ B\ is\ true \\\\&0,otherwise\end{aligned}\right.$$

$\gcd(i,j)$ is the greatest common divisor of $i$ and $j$.

We define $f(i)=\displaystyle \sum_{j=1}^{i-1} [S[1:j]==S[i-j+1:i]]\times \gcd(i,j)$.

Now ask for the value of $\displaystyle \prod _{i=1}^n(f(i)+1)$ modulo $998\ 244\ 353$.

Input

The first line of input is a positive integer $T(T\leq 10)$ representing the number of test cases.

For each case,input a string $S$ of lowercase letters, no longer than $10^6$.

Output

For each case, output a line with a positive integer representing the answer.


Notes:
In this problem, you may need more stack space to pass this problem.
We suggest you to add the following code into your main function if you use C++.

```
int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
...
exit(0);
}

```

And if you use the code above please $\textbf{DON'T forget to add exit(0)}$; in the end of your main function, otherwise your code may get RE.

5
aaaaa
aabaab
abcdefghi
abaabaaba
abbabbabb

150
48
1
3840
1344