A. A simple problem
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of different strings of length $$$k$$$ that you can get by concatenating prefixes of a given string $$$S$$$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2000$$$)  — the number of test cases. The description of test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq k \leq 2000$$$)  — the length of $$$S$$$ and the size of the desired strings.

The second line contains a string $$$S$$$ consisting of $$$n$$$ lowercase letters. It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print a line with one integer  — the answer to the problem. Since the answer may be huge, print it modulo $$$998244353$$$.

Example
Input
4
5 7
aaaaa
4 4
abcd
3 3
aba
7 15
abacaba
Output
1
8
3
2809