8474: String

There is a string of length n, S[l..r] represents the string concatenated from the lth character to the rth
character, and S len is the length of the string(S[1..S len ] represents the whole S string).
We define F G as the number of positive integers x that satisfy the following conditions:
1. 1 ≤ x ≤ G len
2. G[1,x] = G[G len − x + 1,G len ]
3. The length of the common part of the intervals [1,x] and [G len − x + 1,G len ] is greater than 0 and is
divisible by k.
Now ask for the value of
Q n
i=1 (F S[1..i] + 1) modulo 998244353.

The first line of input is a positive integer T(T ≤ 10) representing the number of data cases.
For each cases:
first line input a string S of lowercase letters, no longer than 10 6 .
second line input a positive integer k(1 ≤ k ≤ S len ).

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

Note that the stack space of the judge system is a bit small, please pay attention to the reasonable
allocation of memory.