#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=1000010;
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
	);
}
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;
	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;
				for(int j=1;j<o;j++){
					int p=(i-1)*o+1;
					puu x=gethas(p-j,p-1);
					int q=(i+k-2)*o;
					puu y=gethas(q+1,q+o-j);
					puu z=mp(
						(y.fi*bas1[j]%mod1+x.fi)%mod1,
						(y.se*bas2[j]%mod2+x.se)%mod2
					);
					if(z==a[i])
						++ans;
				}
			}
		}
	}
	cout<<ans<<'\n';
}
signed main(){
//	freopen("data.in","r",stdin); 
//	freopen("data.out","w",stdout); 
	int T;read(T);
	while(T--)solve();
	return 0;
}