There is a string of length n, S[l..r] represents the string concatenated from the lth character to the rth character, and Slen is the length of the string S[1..Slen] represents the whole S string).
We define FG as the number of positive integers x that satisfy the following conditions:
1≤x≤Glen
G[1,x]=G[Glen−x+1,Glen]
The length of the common part of the intervals [1,x] and ][Glen−x+1,Glen] is greater than 0 and is divisible by k.
Now ask for the value of ∏i=1n(FS[1..i]+1) modulo 998244353.
Sample Input
1
abababac
2
Sample Output
24
Hint
Note that the stack space of the judge system is a bit small, please pay attention to the reasonable allocation of memory.
输入格式
Input
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 106.
second line input a positive integer k(1≤k≤Slen).
输出格式
Output
For each cases, output a line with a positive integer representing the answer.