给定一个长度为 $n$ 的字符串，用 $S[l..r]$ 表示从第 $l$ 个字符到第 $r$ 个字符连接而成的子串，$S_{len}$ 表示字符串的长度（$S[1..S_{len}]$ 表示整个字符串 $S$）。

我们定义 $F_G$ 为满足以下条件的整数 $x$ 的个数： 1. $1 \le x \le G_{len}$ 2. $G[1, x] = G[G_{len} - x + 1, G_{len}]$ 3. 区间 $[1, x]$ 和 $[G_{len} - x + 1, G_{len}]$ 的公共部分的长度大于 $0$ 且能被 $k$ 整除。

现在请求出 $\prod_{i=1}^{n} (F_{S[1..i]} + 1) \pmod{998244353}$ 的值。

输入格式

第一行输入一个正整数 $T (T \le 10)$，表示数据组数。 对于每组数据： 第一行输入一个由小写字母组成的字符串 $S$，长度不超过 $10^6$。 第二行输入一个正整数 $k (1 \le k \le S_{len})$。

输出格式

对于每组数据，输出一行，包含一个正整数表示答案。

样例

输入格式 1

1
abababac
2

输出格式 1

24

说明

注意，评测系统的栈空间较小，请注意合理分配内存。