#include <bits/stdc++.h>
using namespace std;
 
typedef signed long long ll;
const ll p = 11;
const ll mod = 1e9 + 7;
const int MX = 1e6 + 5;
int t, n, k;
ll _hash[MX], P[MX];
char str[MX];
string tmp;
map<ll, int > H;
 
 
ll get_hash(int st, int len){
	ll Ans = (_hash[st + len - 1] - (_hash[st - 1] * P[len]) % mod) % mod;
	if(Ans <= 0) Ans += mod;
	return Ans;
}
 
int main() {
	P[0] = 1;
	for(int i = 1; i < MX; P[i] = (P[i - 1] * p) % mod, i++);
	scanf("%d", &t);
 
	for(int i = 1; i <= t; i++){
		scanf("%d %d %s", &n, &k, str);
 
		_hash[0] = (ll)str[0]; H.clear();
		for(int j = 1; j < n; j++){
			_hash[j] = ((_hash[j - 1] * p) % mod + str[j]) % mod;
		}
 
		H[_hash[k - 1]]++;
		for(int j = 1; j <= n - k; j++){
			ll h = get_hash(j, k);
			H[h]++;
		}
 
		printf("%d\n", H.size());
	}
 
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHNpZ25lZCBsb25nIGxvbmcgbGw7CmNvbnN0IGxsIHAgPSAxMTsKY29uc3QgbGwgbW9kID0gMWU5ICsgNzsKY29uc3QgaW50IE1YID0gMWU2ICsgNTsKaW50IHQsIG4sIGs7CmxsIF9oYXNoW01YXSwgUFtNWF07CmNoYXIgc3RyW01YXTsKc3RyaW5nIHRtcDsKbWFwPGxsLCBpbnQgPiBIOwoKCmxsIGdldF9oYXNoKGludCBzdCwgaW50IGxlbil7CglsbCBBbnMgPSAoX2hhc2hbc3QgKyBsZW4gLSAxXSAtIChfaGFzaFtzdCAtIDFdICogUFtsZW5dKSAlIG1vZCkgJSBtb2Q7CglpZihBbnMgPD0gMCkgQW5zICs9IG1vZDsKCXJldHVybiBBbnM7Cn0KCmludCBtYWluKCkgewoJUFswXSA9IDE7Cglmb3IoaW50IGkgPSAxOyBpIDwgTVg7IFBbaV0gPSAoUFtpIC0gMV0gKiBwKSAlIG1vZCwgaSsrKTsKCXNjYW5mKCIlZCIsICZ0KTsKCQoJZm9yKGludCBpID0gMTsgaSA8PSB0OyBpKyspewoJCXNjYW5mKCIlZCAlZCAlcyIsICZuLCAmaywgc3RyKTsKCQkKCQlfaGFzaFswXSA9IChsbClzdHJbMF07IEguY2xlYXIoKTsKCQlmb3IoaW50IGogPSAxOyBqIDwgbjsgaisrKXsKCQkJX2hhc2hbal0gPSAoKF9oYXNoW2ogLSAxXSAqIHApICUgbW9kICsgc3RyW2pdKSAlIG1vZDsKCQl9CgkJCgkJSFtfaGFzaFtrIC0gMV1dKys7CgkJZm9yKGludCBqID0gMTsgaiA8PSBuIC0gazsgaisrKXsKCQkJbGwgaCA9IGdldF9oYXNoKGosIGspOwoJCQlIW2hdKys7CgkJfQoJCQoJCXByaW50ZigiJWRcbiIsIEguc2l6ZSgpKTsKCX0KCQoJCglyZXR1cm4gMDsKfQ==

NQozIDIKYWFhCjUgMQphYmNiYQo0IDIKYWJhYwoxMCAyCmFiYmFhYWFiYmEKNyAzCmRvZ29kb2c=

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