Problem Description

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\leq x\leq 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 $\prod_{i=1}^n (F_{S[1..i]}+1)$ modulo $998244353$.

Input

The first line of input is a positive integer $T(T\leq 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 \leq k \leq S_{len})$.

Output

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

1
abababac
2

24

Hint

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