#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+10;
int _,n,m;
int rk[N],sa[N],hei[N];
char s[N];
namespace SA{
	int m,x[N],y[N],c[N],mn[N][18],lg[N];
	void get_sa(){
		m=131;
		for(int i=1;i<=m;i++)c[i]=0; 
		memset(rk,0,(n+1)*sizeof(int));
		memset(y,0,(n+1)*sizeof(int));
		memset(x,0,(n+1)*sizeof(int));
		memset(c,0,max(m+1,n+1)*sizeof(int));
		for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
		int l=0;
		for(int i=1;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i>=1;i--)sa[c[s[i]]--]=i;
		for(int k=1;k<=n;k<<=1){
			int num=0;
			for(int i=n-k+1;i<=n;i++)y[++num]=i;
			for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
			for(int i=1;i<=m;i++)c[i]=0;
			for(int i=1;i<=n;i++)c[x[i]]++;
			for(int i=2;i<=m;i++)c[i]+=c[i-1];
			for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
			swap(x,y);
			num=1,x[sa[1]]=1;
			for(int i=2;i<=n;i++){
				if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
				else x[sa[i]]=++num; 
			}
			if(num==n)break;
			m=num;
		}
		for(int i=1;i<=n;i++)rk[sa[i]]=i;
		for(int i=1,k=0;i<=n;i++){
			int j=sa[rk[i]-1];k-=(k!=0);
			while(s[i+k]==s[j+k])++k;
			hei[rk[i]]=k;
		}
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
		for(int i=1;i<=n;i++){
			mn[i][0]=hei[i];
			for(int j=1;i>>j;j++)mn[i][j]=min(mn[i][j-1],mn[i-(1<<j-1)][j-1]);
		}
	}
	int lcp(int l,int r){
		l=rk[l],r=rk[r];
		if(l>r)swap(l,r);++l;
		int d=lg[r-l+1];
		return min(mn[r][d],mn[l+(1<<d)-1][d]);
	}
}
using SA::lcp;
struct Bit{
	int vis[N],st[N],tp,c[N];
	void ins(int i,int v){
		for(;i<=n;i+=i&-i){
			if(!vis[i])vis[i]=1,st[++tp]=i;
			c[i]+=v;
		}
	}
	int qry(int i){
		int s=0;
		for(;i;i&=i-1)s+=c[i];
		return s;
	}
	void clr(){
		for(;tp;--tp)vis[st[tp]]=c[st[tp]]=0;
	}
}T;
struct que{
	int l,r,i;
	bool operator<(const que h)const{return r<h.r;}
}ql[N],qr[N];
vector<que> q1[N],q2[N];
int ans[N];
namespace Conquer{
	int s[N];
	void solve(int l,int r){
		if(l==r)return;
		int mid=l+r>>1;solve(l,mid),solve(mid+1,r);
		s[mid]=s[mid+1]=hei[mid+1];
		for(int i=mid-1;i>=l;i--)s[i]=min(s[i+1],hei[i+1]);
		for(int i=mid+2;i<=r;i++)s[i]=min(s[i-1],hei[i]);
//		for(int i=l;i<=mid;i++)for(que t:q1[i]){
//			for(int j=mid+1;j<=r;j++){
//				if(sa[j]>t.l&&sa[j]<=t.r&&min(s[i],s[j])>=t.r-sa[j]+1)++ans[t.i];
//			}
//		}
//		return;
		int tl=0,tr=0;
		for(int i=mid;i>=l;i--){
			for(que t:q1[i]){
				int L=max(t.l+1,r-s[i]+1),R=t.r;
				if(L<=R)ql[++tl]={L,R,t.i};
			}
		}
		for(int i=mid+1;i<=r;i++)qr[++tr]={sa[i],sa[i]+s[i],i};
		sort(ql+1,ql+tl+1),sort(qr+1,qr+tr+1);
		int p=tr;
		for(int i=tl;i>=1;i--){
			while(p&&qr[p].r>ql[i].r)T.ins(qr[p].l,1),--p;
			ans[ql[i].i]+=T.qry(ql[i].r)-T.qry(ql[i].l-1);
		}
		T.clr();
	}
}
signed main(){
	scanf("%d",&_);
	for(;_--;){
		scanf("%d%d\n%s",&n,&m,s+1);
		SA::get_sa();
//		for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
//		for(int i=1;i<=n;i++)printf("%d ",hei[i]);puts("");
		for(int i=1;i<=n;i++)q1[i].clear(),q2[i].clear(); 
		for(int i=1,l,r,k;i<=m;i++){
			scanf("%d%d%d",&l,&r,&k),ans[i]=1;
			int L=0,R=rk[k];
			while(L+1<R){
				int mid=L+R>>1;
				if(lcp(k,sa[mid])>=r-k+1)R=mid;
				else L=mid;
			}
			if(k>l)q2[L].push_back({l,k-1,i});
			if(k<r)q2[rk[k]].push_back({k+1,r,i});
			q1[rk[k]].push_back({k,r,i});
		}
		for(int i=1;i<=n;i++){
			T.ins(sa[i],1);
			for(que t:q2[i])ans[t.i]+=T.qry(t.r)-T.qry(t.l-1);
		}
		T.clr();
		Conquer::solve(1,n);
		for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	}
}