#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 50000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,l,r,op;
};
struct rds
{
	int l,r,d;
};
rds delta[N+1],delta2[N+1];
struct node
{
	int num,data;
};
int T,n,m,length,ST[N+1][21],cl[N+1],sl[N+1],sr[N+1],sk[N+1],cs[N+1],lg[N+1],num[N+1],sa[N+1],rk[N+1],tmp[N+1],cnt[N+1],scnt[N+1],h[N+1],ans[N+1],tong[N+1];
char c[N+1];
vector<reads>p[N+1];
vector<rds>rst[N+1];
vector<node>A[N+1];
vector<node>B[N+1];
void build_SA()
{
	for (int i=1;i<=26;++i) cnt[i]=0;
	for (int i=1;i<=n;++i) num[i]=++cnt[c[i]-'a'+1];
	for (int i=1;i<=26;++i) scnt[i]=scnt[i-1]+(cnt[i]>0),cnt[i]+=cnt[i-1];
	for (int i=1;i<=n;++i) rk[i]=scnt[c[i]-'a'+1],sa[num[i]+cnt[c[i]-'a']]=i;
	length=scnt[26];
	for (int i=1;length<n;i<<=1)
	{
		for (int j=1;j<=length;++j) cnt[j]=0;
		for (int j=n-i+1;j<=n;++j) num[j]=++cnt[rk[j]];
		for (int j=1;j<=n;++j)
			if (sa[j]>=i+1)
				num[sa[j]-i]=++cnt[rk[sa[j]-i]];
		for (int j=1;j<=length;++j) cnt[j]+=cnt[j-1];
		for (int j=1;j<=n;++j) sa[num[j]+cnt[rk[j]-1]]=j;
		length=0;
		for (int j=1;j<=n;++j)
		{
			if (j==1||rk[sa[j]]!=rk[sa[j-1]]||(sa[j]+i<=n?rk[sa[j]+i]:0)!=(sa[j-1]+i<=n?rk[sa[j-1]+i]:0)) ++length;
			tmp[sa[j]]=length;
		}
		for (int j=1;j<=n;++j) rk[j]=tmp[j];
	}
	for (int i=1;i<=n;++i)
	{
		h[rk[i]]=max(h[rk[i-1]]-1,0);
		if (sa[i]!=1)
		{
			while (max(i,rk[sa[i]-1])+h[rk[i]]<=n&&c[i+h[rk[i]]]==c[rk[sa[i]-1]+h[rk[i]]]) h[rk[i]]++;
		}
	}
	return;
}
int query(int l,int r)
{
	int lw=lg[r-l+1];
	return min(ST[l][lw],ST[r-(1<<lw)+1][lw]);
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int d)
{
	for (;x<=n;x+=lowbit(x)) cs[x]+=d;
	return;
}
int get_sum(int x)
{
	int res=0;
	for (;x>=1;x-=lowbit(x)) res+=cs[x];
	return res;
}
bool check(int x,rds d)
{
	if (d.l==d.r) return x==d.l;
	else return d.l<=x&&x<=d.r&&(x-d.l)%d.d==0;
}
rds get_cross(rds a,rds b)
{
	if (a.l==a.r)
	{
		if (check(a.l,b)) return a;
		else return (rds){-1,-1,-1};
	}
	else if (b.l==b.r)
	{
		if (check(b.l,a)) return b;
		else return (rds){-1,-1,-1};
	}
	else if (a.l+a.d==a.r)
	{
		int op=check(a.l,b),op2=check(a.r,b);
		if (op&&op2) return a;
		else if (op&&!op2) return (rds){a.l,a.l,0};
		else if (!op&&op2) return (rds){a.r,a.r,0};
		else return (rds){-1,-1,-1};
	}
	else if (b.l+b.d==b.r)
	{
		int op=check(b.l,a),op2=check(b.r,a);
		if (op&&op2) return b;
		else if (op&&!op2) return (rds){b.l,b.l,0};
		else if (!op&&op2) return (rds){b.r,b.r,0};
		else return (rds){-1,-1,-1};
	}
	else
	{
		if (max(a.l,b.l)<=min(a.r,b.r)) return (rds){max(a.l,b.l),min(a.r,b.r),a.d};
		else return (rds){-1,-1,-1};
	}
}
void solve()
{
	int pv,tl,tr,nw;
	rds d;
	for (int i=1;i<=n;i<<=1)
	{
		pv=1;
		for (int j=1;j<=n;++j)
		    if (j==n||h[j+1]<i)
			{
				if (sa[j]<=n-i+1)
				{
					length=0;
					for (int k=pv;k<=j;++k) tong[++length]=sa[k];
					sort(tong+1,tong+length+1);
					for (int k=1;k<=length;++k)
					{
						nw=tong[k];
						for (int t=0;t<A[nw].size();++t)
						{
							if (i<=A[nw][t].data-nw+1)
							{
								tl=lower_bound(tong+1,tong+length+1,A[nw][t].data-(i<<1)+2)-tong,tr=lower_bound(tong+1,tong+length+1,A[nw][t].data-i+2)-tong-1;
								if (tl<=tr)
								{
									if (tl==tr) delta[A[nw][t].num]=(rds){A[nw][t].data-tong[tl]+1,A[nw][t].data-tong[tl]+1,0};
									else delta[A[nw][t].num]=(rds){A[nw][t].data-tong[tr]+1,A[nw][t].data-tong[tl]+1,(tong[tr]-tong[tl])/(tr-tl)};
								}
								else delta[A[nw][t].num]=(rds){-1,-1,-1};
							}
						}
					}
					for (int k=1;k<=length;++k)
					{
						nw=tong[k]+i-1;
						for (int t=0;t<B[nw].size();++t)
							if (i<=nw-B[nw][t].data+1)
							{
								tl=lower_bound(tong+1,tong+length+1,B[nw][t].data)-tong,tr=lower_bound(tong+1,tong+length+1,B[nw][t].data+i)-tong-1;
								if (B[nw][t].num==2) cerr<<tl<<"!@!#!@!"<<tr<<endl;
								if (tl<=tr)
								{
									if (tl==tr) delta2[B[nw][t].num]=(rds){tong[tl]-B[nw][t].data+i,tong[tl]-B[nw][t].data+i,0};
									else delta2[B[nw][t].num]=(rds){tong[tl]-B[nw][t].data+i,tong[tr]-B[nw][t].data+i,(tong[tr]-tong[tl])/(tr-tl)};
								}
								else delta2[B[nw][t].num]=(rds){-1,-1,-1};
							}
					}
				}
				pv=j+1;
			}
		for (int j=1;j<=m;++j)
			if (sr[j]!=n&&i<=sr[j]-sk[j]+1&&delta[j].l!=-1&&delta2[j].l!=-1)
			{
				d=get_cross(delta[j],delta2[j]);
				if (d.l!=-1) rst[j].push_back(d);
			}
	}
	return;
}
int main()
{
	int l,r,k,d;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	T=read();
	while (T--)
	{
		n=read(),m=read();
		for (int i=1;i<=n;++i) cin>>c[i],cs[i]=0,p[i].clear(),A[i].clear(),B[i].clear();
		build_SA();
		for (int i=1;i<=n;++i) ST[i][0]=h[i];
		for (int i=1;i<=lg[n];++i)
			for (int j=1;j+(1<<i)-1<=n;++j)
				ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
		for (int i=1;i<=m;++i)
		{
			sl[i]=l=read(),sr[i]=r=read(),sk[i]=k=read(),d=rk[k],ans[i]=1,rst[i].clear();
			for (int j=lg[n];j>=0;--j)
				if (d-(1<<j)>=1&&query(d-(1<<j)+1,rk[k])>=r-k+1)
					d-=(1<<j);
			if (1<=rk[k]-1) p[r].push_back((reads){i,1,rk[k]-1,1}),p[l-1].push_back((reads){i,1,rk[k]-1,-1});
			if (l<=k-1&&d<=rk[k]-1) p[k-1].push_back((reads){i,d,rk[k]-1,-1}),p[l-1].push_back((reads){i,d,rk[k]-1,1});
			if (r!=n) A[k].push_back((node){i,r}),B[r].push_back((node){i,k});
		}
		solve();
		for (int i=1;i<=n;++i)
		{
			add(rk[i],1);
			for (int j=0;j<p[i].size();++j) ans[p[i][j].num]+=(get_sum(p[i][j].r)-get_sum(p[i][j].l-1))*p[i][j].op;
		}
		for (int i=1;i<=m;++i)
			for (int j=0;j<rst[i].size();++j)
			{
			    if (!rst[i][j].d)
				{
					if (rst[i][j].l<=sr[i]-sk[i])
					{
						if (sa[sr[i]-rst[i][j].l+1]>sa[sk[i]]) ans[i]++;
					}
				}
				else
				{
					if (rst[i][j].l<=min(rst[i][j].r,sr[i]-sk[i]))
					{
						if (sa[sr[i]-rst[i][j].l+1]>sa[sk[i]]) ans[i]+=(min(rst[i][j].r,sr[i]-sk[i])-rst[i][j].l)/rst[i][j].d+1;
					}
				}
			}
		for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
	}
	return 0;
}