You are given an integer ~k~ and a string ~s~ of length ~n~. Imagine writing out all ~2^n - 1~ non-empty subsequences~^\dagger~ of ~s~. Count the number of different strings ~t~ that were written down exactly ~k~ times. Because the answer can be huge, you need to output it modulo ~998\,244\,353~.

~^\dagger~ A string ~t~ is a subsequence of ~s~ if there is a way to erase some (possibly zero) characters from ~s~ to obtain ~t~.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~), followed by ~k~ (~1 \leq k \leq 2~), the intended number of occurrences, which is the same for every test case. The description of each test case is as follows.

The first line of each test case contains ~n~ (~1 \le n \le 3 \cdot 10^5~) describing the length of string ~s~.

The second line of each test case contains the string ~s~ consisting of ~n~ lowercase Latin characters.

The sum of ~n~ in all test cases is guaranteed not to exceed ~3 \cdot 10^5~.

Output

For each test case, print one integer — the number of strings that have exactly ~k~ occurrences as a subsequence in ~s~, modulo ~998\,244\,353~.

Scoring

Sample Input 1

3 2
3
aab
10
vnoihaibon
35
hiiamcurrentlyafirstyearphdstudents

Sample Output 1

2
74
911464594

Sample Input 2

3 1
3
aab
7
vnoicup
38
asomewhatnotshortblogonflowwithdemands

Sample Output 2

3
127
395878133

Notes

The first test case of both examples has ~s = \mathtt{aab}~. All non-empty subsequences of ~s~ are ~[\mathtt{a}, \mathtt{a}, \mathtt{b}, \mathtt{aa}, \mathtt{ab}, \mathtt{ab}, \mathtt{aab}]~. Among these, ~\mathtt{b}~, ~\mathtt{aa}~, and ~\mathtt{aab}~ appears once, while ~\mathtt{a}~ and ~\mathtt{ab}~ appears twice.