#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
#include<cstring>
#include<random>
#include<functional>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr<<"In the line "<<__LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In the line "<<__LINE__<<" the "<<#x<<" = "<<x<<" the "<<#y<<" = "<<y<<'\n';
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ull,ull> puu;
typedef vector<int> vi;
template<typename T>T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int N=2000010;
const int mod1=998244353;
const int mod2=1000000009;
const int base1=233;
const int base2=29;
int n,k;
char s[N];
ull bas1[N],bas2[N],has1[N],has2[N];
puu a[N];
puu gethas(int l,int r){
	return mp(
		(has1[r]-has1[l-1]*bas1[r-l+1]%mod1+mod1)%mod1,
		(has2[r]-has2[l-1]*bas2[r-l+1]%mod2+mod2)%mod2
	);
}
struct SA{
	int bac[N],sa[N],rk[N],SA[N],RK[N];
	int h[N],hight[N];
	int st[20][N],lg[N];
	int LCP(int x,int y){
		x=rk[x],y=rk[y];
		if(x>y)swap(x,y);
		++x;
		int k=lg[y-x+1];
		return min(st[k][x],st[k][y-(1<<k)+1]);
	}
	void getSA(char *str){
		for(int i=0;i<=2*n;i++)sa[i]=rk[i]=SA[i]=RK[i]=h[i]=hight[i]=0;
		for(int i=0;i<=26;i++)bac[i]=0;
		for(int i=1;i<=n;i++)bac[str[i]-'a']++;
		for(int i=1;i<=26;i++)bac[i]+=bac[i-1];
		for(int i=1;i<=n;i++)sa[bac[str[i]-'a']--]=i;
		for(int i=1;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
		for(int p=1;p<=n;p<<=1) {
			for(int i=1;i<=n;i++)bac[rk[sa[i]]]=i;
			for(int i=n;i>=1;i--)
				if(sa[i]>p)
					SA[bac[rk[sa[i]-p]]--]=sa[i]-p;
			for(int i=n;i>n-p;i--)SA[bac[rk[i]]--]=i;
			#define comp(x,y) (rk[x]!=rk[y] || rk[x+p]!=rk[y+p]) 
			for(int i=1;i<=n;i++)RK[SA[i]]=RK[SA[i-1]]+comp(SA[i],SA[i-1]);
			#undef comp
			for(int i=1;i<=n;i++)sa[i]=SA[i],rk[i]=RK[i];
			if(rk[sa[n]]>=n)break;
		}
		for(int i=1;i<=n;i++){
			int j=sa[rk[i]-1],k=max(0,h[i-1]-1);
			while(i+k<=n && j+k<=n && str[i+k]==str[j+k])++k;
			h[i]=hight[rk[i]]=k;
		}
		for(int i=1;i<=n;i++)st[0][i]=hight[i];
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
		for(int i=1;i<20;i++)
			for(int j=1;j+(1<<i)-1<=n;j++)
				st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	}
}Z,F;
void solve(){
	read(k);
	scanf("%s",s+1);n=strlen(s+1);
	if(k==1){
		ll s=1ll*n*(n+1)/2;
		cout<<s<<'\n';
		return ;
	}
	bas1[0]=1;for(int i=1;i<=n;i++)bas1[i]=bas1[i-1]*base1%mod1;
	bas2[0]=1;for(int i=1;i<=n;i++)bas2[i]=bas2[i-1]*base2%mod2;
	has1[0]=1;for(int i=1;i<=n;i++)has1[i]=(has1[i-1]*base1%mod1+s[i])%mod1;
	has2[0]=1;for(int i=1;i<=n;i++)has2[i]=(has2[i-1]*base2%mod2+s[i])%mod2;
	Z.getSA(s);
	reverse(s+1,s+n+1);
	F.getSA(s);
	int ans=0;
	for(int o=1;o<=n;o++){
		int c=0;
		for(int i=1;i+o-1<=n;i+=o){
			a[++c]=gethas(i,i+o-1);
		}
		for(int i=1;i+k-2<=c;i++){
			bool fl=1;
			for(int j=1;j<k;j++)
				if(a[i]!=a[i+j-1]){
					fl=0;
					break;
				}
			if(fl){
				if(i+k-1<=c && a[i+k-1]==a[i]){
					++ans;
//					dpi(o,i);
				}
				if(i>1){
					int len1=Z.LCP((i-1)*o+1,(i+k-2)*o+1);
					int p=(i-1)*o,q=(i+k-2)*o;
					int len2=F.LCP(n-p+1,n-q+1);
					int r=min(len1,o-1),l=max(o-len2,1);
					ans+=max(0,min(r-l+1,o-1));
//					if(max(0,min(r-l+1,o-1))){
//						dpi(l,r);
//					}
				}
			}
		}
	}
	cout<<ans<<'\n';
}
signed main(){
//	freopen("data.in","r",stdin); 
//	freopen("data.out","w",stdout); 
	int T;read(T);
	while(T--)solve();
	return 0;
}