# include <iostream>
# include <vector>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <set>
# include <map>
# include <string>
using namespace std;
string s;
int T, k;
long long p=7;
map<long long,int> S;
map<long long,int>::iterator it;
vector<long long > P(100001);
vector<long long > hashs;
int main(){
	freopen("DEBRUIJN.IN", "r", stdin);
	P[0]=1;
	for(int i=1; i<=100000; i++)
		P[i]=P[i-1]*p;
	cin>>T;
	while(T--){
		cin>>k;
		cin>>s;
		S.clear();
		hashs.clear(), hashs.resize(s.size()+1);
		int ans=0, n=(int)s.size();
		hashs[0]=int(s[0]);
		for(int i=1; i<n; i++){
			hashs[i]=hashs[i-1]+int(s[i])*P[i];
		}
		long long to=(hashs[k])*P[n];
		if(S[to]==0){
			S[to]=1;
		}else{
			S[to]=S[to]+1;	
		}
		for(int i=0; i<n-k; i++){
			long long to=(hashs[i+k]-hashs[i])*P[n-i];
			if(S[to]==0){
				S[to]=1;
			}else{
				S[to]=S[to]+1;	
			}
		}
		for(it = S.begin();it!=S.end();it++){
			if((*it).second>1)ans++;
		}
		cout<<ans<<endl;
	}
}
/*
2
3
ACGT
2
ACTGCTA

*/