问题 H: String and GCD

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]={1,if B is true;      0,otherwise}

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

We define f(i)=j=1∑i−1[S[1:j]==S[i−j+1:i]]×gcd(i,j).

Now ask for the value of i=1∏ n (f(i)+1) modulo $998244353$.

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

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

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 $\text{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