#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
const int N=50007;
char s[N];int sa[N],rk[N],ht[16][N],cnt[N],tt[N];
int msk[20];
void buildsa(int n)
{
	int m=26;sa[n+1]=0;
//	puts(s+1);
	memset(cnt+1,0,m<<2);
	for(int i=1;i<=n;++i)++cnt[rk[i]=s[i]-96];
	for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
	for(int i=1;i<=n;++i)sa[cnt[s[i]-96]--]=i;
	for(int k=1;k<n;k<<=1)
	{
		memset(cnt+1,0,m<<2);for(int i=1;i<=n;++i)++cnt[rk[i]];
		for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
		
		for(int i=n;i;--i)if(sa[i]>k)tt[cnt[rk[sa[i]-k]]--]=sa[i]-k;
		for(int i=n-k+1;i<=n;++i)tt[cnt[rk[i]]--]=i;memcpy(sa+1,tt+1,n<<2);
		for(int i=1;i<=n;++i)tt[sa[i]]=tt[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+k]!=rk[sa[i-1]+k]);
		memcpy(rk+1,tt+1,n<<2);m=rk[sa[n]];
	}
	if(n==1)rk[1]=1;
	for(int i=1,k=0;i<=n;++i)if(rk[i]>1)
	{
		for(k&&--k;s[i+k]==s[sa[rk[i]-1]+k];++k);
		ht[0][rk[i]-1]=k;
	}
//	for(int i=1;i<=n;++i)printf("%d ",sa[i]);puts("]sa");
//	for(int i=1;i<=n;++i)printf("%d ",rk[i]);puts("]rk");
//	for(int i=1;i<n;++i)printf("%d ",ht[0][i]);puts("]ht[0]");
	for(int k=1;k<=15;++k)for(int i=1;i+msk[k]-1<n;++i)
		ht[k][i]=std::min(ht[k-1][i],ht[k-1][i+msk[k-1]]);
}
int ans[N],cbit[N*2];
void cadd(int x,int v){for(;x<=1e5;x+=(x&-x))cbit[x]+=v;}
int csum(int x){int r=0;for(;x;x&=(x-1))r+=cbit[x];return r;}
struct qra{int l,r,id;};
struct qrb{int r,k,id,t;};
struct qrc{int dmx,id,f,t;};
inline bool operator<(qrb x,qrb y){return x.t<y.t;}
inline bool operator<(qrc x,qrc y){return x.t==y.t?x.f<y.f:x.t<y.t;}
std::vector<qra> qa[N];
qrb qb[N];int fi[N];
qrc qc[N*3];int c[N];
void solv(int l,int r)
{
	if(l==r)return;int mid=(l+r)>>1;
	solv(l,mid);solv(mid+1,r);c[mid]=ht[0][mid];
	for(int i=mid+1;i<=r;++i)c[i]=std::min(c[i-1],ht[0][i-1]);
	for(int i=mid;i>=l;--i)c[i]=std::min(c[i+1],ht[0][i]);
	
	if(fi[l-1]==fi[mid])return;
//	printf("l=%d mid=%d r=%d\n",l,mid,r);
	
	int cq=0;
	for(int u=fi[l-1]+1;u<=fi[mid];++u)
	{
		int k=qb[u].k,r=qb[u].r,id=qb[u].id;
//		printf("c[i]=%d i=%d r=%d\n",c[rk[k]],k,r);
		int kl=std::max(k,r-c[rk[k]]);
		qc[++cq]=(qrc){r,id,-1,kl};
		qc[++cq]=(qrc){r,id,+1,r};
	}
	for(int i=mid+1;i<=r;++i)qc[++cq]=(qrc){sa[i]+c[i],0,-10,sa[i]};
	std::sort(qc+1,qc+cq+1);int al=0;
	for(int i=1;i<=cq;++i)
		if(qc[i].f==-10)cadd(qc[i].dmx,1),++al;//,printf("add.qc[i].t=%d\n",qc[i].t);
		else ans[qc[i].id]+=(al-csum(qc[i].dmx))*qc[i].f;//,printf("alf=%dx%d | id=%d t=%d[dmx=%d]\n",al-csum(qc[i].dmx),qc[i].f,qc[i].id,qc[i].t,qc[i].dmx);
	for(int i=mid+1;i<=r;++i)cadd(sa[i]+c[i],-1);
//	puts("");
}
int main()
{
	for(int k=0;k<20;++k)msk[k]=1<<k;
//	freopen("i.in","r",stdin);
//	freopen("wa.out","w",stdout);
	int T,n,m;scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%s",&n,&m,s+1);buildsa(n);
		for(int i=1;i<=n;++i)qa[i].clear();		
		memset(fi+1,0,n<<2);memset(ans+1,0,m<<2);
		for(int i=1;i<=m;++i)
		{
			int l,r,k;scanf("%d%d%d",&l,&r,&k);
			int L=rk[k];for(int p=15;~p;--p)if(L>msk[p]&&ht[p][L-msk[p]]>r-k)L-=msk[p];
			qa[L-1].push_back({l,k-1,i});qa[rk[k]].push_back({k+1,r,i});
			++fi[rk[k]];qb[i]={r,k,i,rk[k]};
		}
		std::sort(qb+1,qb+m+1);for(int i=1;i<=n;++i)fi[i]+=fi[i-1];
		for(int i=1;i<=n;++i){cadd(sa[i],1);for(qra t:qa[i])if(t.l<=t.r)ans[t.id]+=csum(t.r)-csum(t.l-1);}
//		for(int i=1;i<=m;++i)printf("%d ",ans[i]);puts("]");
		for(int i=1;i<=n;++i)cadd(i,-1);solv(1,n);for(int i=1;i<=m;++i)printf("%d\n",ans[i]+1);
	}
	return 0;
}