H. Loose Subsequences
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a string $$$S$$$ of length $$$n$$$ consisting only of lowercase letters, the following conventions are established.

  • Subsequence: A sequence formed by extracting several elements (not necessarily consecutive) from $$$S$$$ without changing their relative positions is called a subsequence.
  • A $$$k$$$-loose subsequence: If any two adjacent characters in a subsequence of $$$S$$$ are at least $$$k$$$ positions apart in the original string $$$S$$$, then this subsequence is called a $$$k$$$-loose subsequence of $$$S$$$. Specifically, for a subsequence $$$T = \overline{S_{pos_{1}}S_{pos_{2}}\cdots S_{pos_{m}}}$$$ of $$$S$$$ of length $$$m$$$, $$$T$$$ is a $$$k$$$-loose subsequence of $$$S$$$ if and only if $$$\forall i \in [1, m - 1]$$$, $$$pos_{i + 1} - pos_{i} \gt k$$$.

Now, given a non-negative integer $$$k$$$, you need to calculate the number of distinct non-empty $$$k$$$-loose subsequences of $$$S$$$, and output the result modulo 998244353.

Two subsequences $$$A$$$ and $$$B$$$ of $$$S$$$ are considered different if and only if $$$|A| \neq |B|$$$ or there exists an index $$$i$$$ such that $$$A_i \neq B_i$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^6$$$), representing the number of test cases.

For each test case, the first line contains two integers $$$n, k$$$ ($$$1\le n \le 10^6, 0\le k \le n$$$), as described in the problem statement.

The second line contains a string $$$S$$$ of length $$$n$$$, guaranteed to consist only of lowercase letters.

It is guaranteed that for all test cases, $$$\sum n \le 10^6$$$.

Output

For each test case, output a single integer on a new line, representing the number of distinct non-empty $$$k$$$-loose subsequences of $$$S$$$, modulo 998244353.

Example
Input
3
4 1
aabb
5 2
abcab
7 3
abcdece
Output
3
6
10
Note

For the first test case, the subsequences a, b, ab meet the requirements.

For the second test case, the subsequences a, b, c, aa, ab, bb meet the requirements.