Nguồn đề : https://www.spoj.com/problems/ADACLEAN/

Cho một chuỗi kí tự s, có độ dài n, và một số nguyên k, hãy tính xem có bao nhiêu chuỗi con phân biệt có độ dài đúng bằng k của chuỗi s.

Chuỗi con của s là một chuỗi kí tự gồm các kí tự liên tiếp trong s.

Input

Dòng 1: t - số lượng test.

Dòng 2: n, k ~(1 ≤ n, k ≤ 10^5).~

Dòng 3: chuỗi kí tự s, bao gồm các chữ cái thường ('a'->'z').

Tổng n của tất cả các test không vượt quá ~10^6~

Kết quả

Với mỗi test in ra số lượng chuỗi kí tự con phân biệt có độ dài đúng bằng k .

Sample Input

5
3 2
aaa
5 1
abcba
4 2
abac
10 2
abbaaaabba
7 3
dogodog

Sample Output

1
3
3
4
4