# include <iostream>
# include <vector>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <set>
# include <map>
# include <string>
using namespace std;
string s;
int T, k;
map<string,int> S;
map<string,int>::iterator it;
int main(){
	freopen("DEBRUIJN.IN", "r", stdin);
	cin>>T;
	while(T--){
		cin>>k;
		cin>>s;
		S.clear();
		int ans=0, n=(int)s.size();
		string to;
		for(int i=0; i<n-k; i++){
			to=s.substr(i, k);
			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
*/