#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,cater,length,ST[N+1][21],p1[N+1],p2[N+1],cl[N+1],clA[N+1],clB[N+1],pl1[N+1],pr1[N+1],pl2[N+1],pr2[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<int>sp[N+1];
vector<int>tp[N+1];
vector<rds>rst[N+1];
vector<node>A[N+1];
vector<node>B[N+1];
vector<node>tA[N+1];
vector<node>tB[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 (rk[i]!=1)
		{
			while (max(i,sa[rk[i]-1])+h[rk[i]]<=n&&c[i+h[rk[i]]]==c[sa[rk[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 calc(int x,int d)
{
	int tl,tr,nw;
	length=0;
	for (int k=0;k<sp[x].size();++k) tong[++length]=sp[x][k];
	tl=1,tr=0;
	for (int k=0;k<tA[x].size();++k)
	{
		while (tl<=length&&tong[tl]<tA[x][k].data-(d<<1)+2) tl++;
		while (tr+1<=length&&tong[tr+1]<=tA[x][k].data-d+1) tr++;
		pl1[tA[x][k].num]=tl,pr1[tA[x][k].num]=tr;
	}
	tl=1,tr=0;
	for (int k=0;k<tB[x].size();++k)
	{
		while (tl<=length&&tong[tl]<tB[x][k].data) tl++;
		while (tr+1<=length&&tong[tr+1]<=tB[x][k].data+d-1) tr++;
		pl2[tB[x][k].num]=tl,pr2[tB[x][k].num]=tr;
	}
	for (int k=1;k<=length;++k)
	{
		nw=tong[k];
		for (int t=0;t<A[nw].size();++t)
			if (d<=A[nw][t].data-nw+1)
			{
				tl=pl1[A[nw][t].num],tr=pr1[A[nw][t].num];
				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]+d-1;
		for (int t=0;t<B[nw].size();++t)
			if (d<=nw-B[nw][t].data+1)
			{
				tl=pl2[B[nw][t].num],tr=pr2[B[nw][t].num];
				if (tl<=tr)
				{
					if (tl==tr) delta2[B[nw][t].num]=(rds){tong[tl]-B[nw][t].data+d,tong[tl]-B[nw][t].data+d,0};
					else delta2[B[nw][t].num]=(rds){tong[tl]-B[nw][t].data+d,tong[tr]-B[nw][t].data+d,(tong[tr]-tong[tl])/(tr-tl)};
				}
				else delta2[B[nw][t].num]=(rds){-1,-1,-1};
			}
	}
	return;
}
void solve()
{
	int pv;
	rds d;
	for (int i=1;i<=n;i<<=1)
	{
		pv=1,cater=0;
		for (int j=1;j<=n;++j) cl[j]=0;
		for (int j=1;j<=m;++j) clA[j]=clB[j]=0;
		for (int j=1;j<=n;++j)
			if (j==n||h[j+1]<i)
			{
				if (sa[j]<=n-i+1)
				{
					++cater,sp[cater].clear(),tA[cater].clear(),tB[cater].clear();
					for (int k=pv;k<=j;++k)
					{
						cl[sa[k]]=cater;
						for (int t=0;t<A[sa[k]].size();++t) clA[A[sa[k]][t].num]=cater;
						for (int t=0;t<B[sa[k]+i-1].size();++t) clB[B[sa[k]+i-1][t].num]=cater;
					}
				}
				pv=j+1;
			}
		for (int j=1;j<=n;++j)
			if (cl[j])
				sp[cl[j]].push_back(j);
		for (int j=1;j<=m;++j)
		{
			if (clA[p1[j]]) tA[clA[p1[j]]].push_back((node){p1[j],sr[p1[j]]});
			if (clB[p2[j]]) tB[clB[p2[j]]].push_back((node){p2[j],sk[p2[j]]});
		}
		for (int j=1;j<=cater;++j) calc(j,i);
		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;
}
bool cmp(int x,int y)
{
	return sr[x]<sr[y];
}
bool cmp2(int x,int y)
{
	return sk[x]<sk[y];
}
int main()
{
	int l,r,k,d,ds,x,op,op2;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	T=read();
	for (int qt=1;qt<=T;++qt)
	{
		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(),p1[i]=p2[i]=i,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});
		}
		sort(p1+1,p1+m+1,cmp),sort(p2+1,p2+m+1,cmp2),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 (rk[sr[i]-rst[i][j].l+1]>rk[sk[i]]) ans[i]++;
					}
				}
				else
				{
					if (rst[i][j].l<=min(rst[i][j].r,sr[i]-sk[i]))
					{
						ds=(min(rst[i][j].r,sr[i]-sk[i])-rst[i][j].l)/rst[i][j].d,op=(rk[sr[i]-rst[i][j].l+1]>rk[sk[i]]),op2=(rk[sr[i]-rst[i][j].l-ds*rst[i][j].d+1]>rk[sk[i]]);
						if (op&&op2) ans[i]+=ds+1;
						else if (op&&!op2)
						{
							x=0;
							for (int k=lg[ds];k>=0;--k)
								if (x+(1<<k)<=ds&&rk[sr[i]-rst[i][j].l-(x+(1<<k))*rst[i][j].d+1]>rk[sk[i]])
									x+=(1<<k);
							ans[i]+=x+1;
						}
						else if (!op&&op2)
						{
							x=ds;
							for (int k=lg[ds];k>=0;--k)
								if (x-(1<<k)>=0&&rk[sr[i]-rst[i][j].l-(x-(1<<k))*rst[i][j].d+1]>rk[sk[i]])
									x-=(1<<k);
							ans[i]+=ds-x+1;
						}
					}
				}
			}
		for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
	}
	return 0;
}