Cho số nguyên ~k~ và xâu ~s~ có độ dài ~n~. Tưởng tượng bạn viết xuống toàn bộ ~2^n - 1~ dãy con không rỗng~^\dagger~ của xâu ~s~. Hãy đếm số lượng xâu ~t~ khác nhau được viết xuống đúng ~k~ lần. Vì kết quả có thể rất lớn, bạn cần tính theo modulo ~998\,244\,353~.

~^\dagger~ Một xâu ~t~ là một dãy con của xâu ~s~ nếu ~t~ có thể được thu được từ ~s~ bằng cách xóa đi một số (có thể là không) ký tự.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 10\,000~), theo sau là số lần xuất hiện dự định ~k~ (~1 \leq k \leq 2~), giống nhau cho mọi test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của xâu ~s~.

Dòng thứ hai chứa xâu ~s~ gồm ~n~ ký tự Latinh in thường.

Đảm bảo rằng tổng của ~n~ qua tất cả các test case không vượt quá ~3 \cdot 10^5~.

Output

Với mỗi test case, in ra một số nguyên là số lượng xâu xuất hiện chính xác ~k~ lần như một dãy con trong ~s~, theo 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

Test case đầu tiên của cả hai ví dụ có ~s = \mathtt{aab}~. Toàn bộ các dãy con không rỗng của ~s~ là ~[\mathtt{a}, \mathtt{a}, \mathtt{b}, \mathtt{aa}, \mathtt{ab}, \mathtt{ab}, \mathtt{aab}]~. Ta có thể thấy ~\mathtt{b}~, ~\mathtt{aa}~, và ~\mathtt{aab}~ xuất hiện một lần, còn ~\mathtt{a}~ và ~\mathtt{ab}~ xuất hiện hai lần.