雨阶共鸣

题号：NC318519
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

钟楼里的光线又暗，台阶在眼前一层层模糊成影。雨声贴着墙壁回响，她只好微微眯起眼，小步试探着往下走。他放慢了脚步，两人间的空隙被悄然填补。她看不清路，却更靠近了他一点，像是撞进了一段不可言说的心事。钟声沉沉回荡，空气里满是潮湿的安静，隐秘的情绪却已酝酿，被悉数读懂。
他们一共走下了 $n$ 级台阶。每一级台阶上的脚步声、雨声与钟声交织在一起，形成一个下标从 $1$ 开始的长度为 $n$ 的小写字母字符串 $S$ 。
为了描述钟楼中的回声，记 $S$ 中第 $l$ 个字符到第 $r$ 个字符构成的子串为 $S[l,r]$ ，记前缀 $P_x = S[1, x]$ 。
定义函数 $\lambda(x)$ 表示 $P_x$ 的最长影子长度：
$\lambda(x)=\max\{y \mid 0 \le y < x,\ S[1, y] = S[x-y+1, x]\}$
即 $\lambda(x)$ 为最大的小于 $x$ 的非负整数 $y$ 满足 $S[1,y]=S[x-y+1,x]$ 。特别地，若不存在 $y>0$ 满足条件，则 $\lambda(x)=0$ 。
再定义函数 $\rho(x)$ 表示 $P_x$ 的回声阶数：
$\rho(x) = \left\{\begin{matrix} 0, & x=0 \\ 0, & \lambda(x)=0 \\ 0, & 2\lambda(x)<x \\ \rho(\lambda(x))+1, & \mathrm{else} \end{matrix}\right.$
即 $x=0$ 或 $\lambda(x)=0$ 或 $2\lambda(x)<x$ 时 $\rho(x)=0$ ，否则 $\rho(x)=\rho(\lambda(x))+1$ 。
也就是说，只有当一个前缀的最长影子至少覆盖自身一半时，这段影子才足够清晰，可以继续向更深处回响。
现在你需要将整个字符串 $S$ 划分成若干个非空连续片段：
$S=T_1+T_2+\cdots+T_m$
一次划分被称为合法，当且仅当每个片段 $T_i$ 都满足：
1. 存在某个整数长度 $\ell_i$ 满足 $1\leq \ell_i\leq n$ ，使得 $T_i = P_{\ell_i}$ ，即每段是一个原串 $S$ 的前缀。
2. 该长度的回声阶数不少于 $k$ ，即 $\rho(\ell_i) \ge k$ 。
请计算合法划分方案数。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

输入描述:

第一行一个整数  ，表示数据组数。
对于每组数据，第一行两个整数  。
第二行一个长度为  的仅包含小写英文字母的字符串 。
保证单个测试点内所有数据中  的和不超过 。

输出描述:

对于每组数据，输出一行一个整数，表示合法划分方案数对  取模后的结果。

示例1

输入

复制

3
5 0
ababa
4 1
aaaa
4 2
aaaa

输出

复制

4
2
1