给定一个长度为 $n$ 且仅由小写字母组成的字符串 $S$，我们建立以下约定：

• 子序列：从 $S$ 中提取若干元素（不一定连续）且不改变它们相对位置所形成的序列称为子序列。
• $k$-松散子序列：如果一个 $S$ 的子序列中任意两个相邻字符在原字符串 $S$ 中的位置至少相隔 $k$ 个位置，则称该子序列为 $S$ 的 $k$-松散子序列。具体而言，对于 $S$ 的一个长度为 $m$ 的子序列 $T = S_{pos_1}S_{pos_2}\cdots S_{pos_m}$，$T$ 是 $S$ 的 $k$-松散子序列，当且仅当 $\forall i \in [1, m - 1], pos_{i+1} - pos_i > k$。

现在，给定一个非负整数 $k$，你需要计算 $S$ 的不同非空 $k$-松散子序列的数量，并将结果对 $998244353$ 取模。

如果两个子序列 $A$ 和 $B$ 满足 $|A| \neq |B|$ 或者存在某个索引 $i$ 使得 $A_i \neq B_i$，则认为它们是不同的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, k$ ($1 \le n \le 10^6, 0 \le k \le n$)，含义如题目描述所述。

第二行包含一个长度为 $n$ 的字符串 $S$，保证仅由小写字母组成。

保证对于所有测试用例，$\sum n \le 10^6$。

输出格式

对于每个测试用例，输出一行，表示 $S$ 的不同非空 $k$-松散子序列的数量，对 $998244353$ 取模。

样例

输入 1

3
4 1
aabb
5 2
abcab
7 3
abcdece

输出 1

3
6
10

说明

对于第一个测试用例，子序列 a, b, ab 符合要求。

对于第二个测试用例，子序列 a, b, c, aa, ab, bb 符合要求。