#include<cstdio>
#define lg(x) (31-__builtin_clz(x))
const int N=300086;
const long long p1=29,p2=31;
const long long MOD1=1e9+7,MOD2=1004535809;
int s[N];
long long h1[N],h2[N],pw1[N],pw2[N];
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
long long gsh1(int l,int r){return(h1[r]-h1[l-1]*pw1[r-l+1]%MOD1+MOD1)%MOD1;}
long long gsh2(int l,int r){return(h2[r]-h2[l-1]*pw2[r-l+1]%MOD2+MOD2)%MOD2;}
bool chk(int l1,int r1,int l2,int r2){return gsh1(l1,r1)==gsh1(l2,r2)&&gsh2(l1,r1)==gsh2(l2,r2);}
bool solve(){
	int K=read(),n=0;
	s[n=1]=getchar();while(s[1]<'a'||s[1]>'z')s[1]=getchar();
	do{s[++n]=getchar();}while(s[n]>='a'&&s[n]<='z');n--;
	pw1[0]=pw2[0]=1;
	for(int i=1;i<=n;i++){
		h1[i]=(h1[i-1]*p1%MOD1+s[i]-'a'+1)%MOD1;
		h2[i]=(h2[i-1]*p2%MOD2+s[i]-'a'+1)%MOD2;
		pw1[i]=pw1[i-1]*p1%MOD1;
		pw2[i]=pw2[i-1]*p2%MOD2;
	}
	if(K==1){
		printf("%lld\n",1ll*n*(n+1)/2);
		return true;
	}
	long long lh1=0,lh2=0,ans=0;
	for(int len=1;len*K<=n;len++){
		int cnt=0;
		for(int i=1;i*len<=n;i++){
			if(i>1&&chk((i-2)*len+1,(i-1)*len,(i-1)*len+1,i*len))cnt++;
			else cnt=1;
			if(cnt<K-1)continue;
			int rpl=(i-K+1)*len,pos=i*len+1;
			int len1=0,len2=0;
			for(int j=lg(len);j+1;j--){
				if(len1+(1<<j)>len||rpl-len2-(1<<j)<0)continue;
				if(chk(rpl-len1-(1<<j)+1,rpl,pos-len1-(1<<j),pos-1))len1+=(1<<j);
			}
			for(int j=lg(len);j+1;j--){
				if(len2+(1<<j)>=len||pos+len2+(1<<j)-1>n)continue;
				if(chk(rpl+1,rpl+len2+(1<<j),pos,pos+len2+(1<<j)-1))len2+=(1<<j);
			}
			if(len1+len2>=len)ans+=len1+len2-len+1;
			lh1=gsh1((i-1)*len+1,i*len);
			lh2=gsh2((i-1)*len+1,i*len);
		}
	}
	printf("%lld\n",ans);
	return true;
}
int main(){
	int T=read();
	while(T--)solve();
}