#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
const int N=50009,L=16;
int n,m,ans[N];
char ch[N];
int buc[N],sa[N],rk[N],SA[N],RK[N];
int h[N],hei[N],st[N][L],lg[N]; 
bool cmp(int A,int B,int k){
	return rk[A]!=rk[B]||(A+k>n?0:rk[A+k])!=(B+k>n?0:rk[B+k]);
}
void suffix_array(){
	for(int i=1;i<=n;i++) buc[ch[i]-'a']++;
	for(int i=1;i<=26;i++) buc[i]+=buc[i-1];
	for(int i=n;i>=1;i--) sa[buc[ch[i]-'a']--]=i;
	for(int i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(ch[sa[i]]!=ch[sa[i-1]]);
	for(int k=1;k<n;k<<=1){
		for(int i=1;i<=n;i++) buc[rk[sa[i]]]=i;
		for(int i=n;i>=1;i--) if(sa[i]>k) SA[buc[rk[sa[i]-k]]--]=sa[i]-k;
		for(int i=n-k+1;i<=n;i++) SA[buc[rk[i]]--]=i;
		for(int i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+cmp(SA[i-1],SA[i],k);
		memcpy(sa,SA,sizeof(sa)); memcpy(rk,RK,sizeof(rk));
	}
	return;
}
void get_height(){
	for(int i=1;i<=n;i++){
		if(rk[i]==1) continue;
		h[i]=max(h[i-1]-1,0);
		while(i+h[i]<=n&&sa[rk[i]-1]+h[i]<=n&&ch[i+h[i]]==ch[sa[rk[i]-1]+h[i]]) h[i]++;
		hei[rk[i]]=h[i];
	}
	lg[1]=0; for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++) st[i][0]=hei[i];
	for(int i=1;i<L;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]);
	return;
}
struct tree{
	int val;
	int ln,rn;
}tr[N*20];
int rt[N],cntnode;
void build(int &node,int pn,int l,int r,int tar){
	node=++cntnode; tr[node]=tr[pn]; tr[node].val++;
	if(l==r) return;
	if(tar<=mid) build(tr[node].ln,tr[pn].ln,l,mid,tar);
	else build(tr[node].rn,tr[pn].rn,mid+1,r,tar);
	return;
}
int query(int node,int mnd,int l,int r,int tarl,int tarr){
//	cout<<node<<" "<<l<<" "<<r<<" "<<tarl<<" "<<tarr<<endl;
	if(tarl<=l&&r<=tarr) return tr[node].val-tr[mnd].val;
	int re=0;
	if(tarl<=mid) re+=query(tr[node].ln,tr[mnd].ln,l,mid,tarl,tarr);
	if(tarr>mid) re+=query(tr[node].rn,tr[mnd].rn,mid+1,r,tarl,tarr); 
	return re;
}
vector<pair<int,int> >q[N];
int mnl[N],mnr[N],p[N];
bool comp(int A,int B){
	return sa[A]+mnr[A]>sa[B]+mnr[B];
}
struct node{
	int pos,r,id;
};
bool cmpp(node A,node B){
	return A.r>B.r;
}
int bit[N];
void add(int x,int val){
	while(x<N){
		bit[x]+=val;
		x+=(x&(-x));
	}
}
int query(int x){
	int re=0;
	while(x){
		re+=bit[x];
		x-=(x&(-x));
	}
	return re;
}
void cdq(int l,int r){
	if(l==r) return;
	cdq(l,mid); cdq(mid+1,r);
	mnl[mid]=N; for(int i=mid-1;i>=l;i--) mnl[i]=min(mnl[i+1],hei[i+1]);
	mnr[mid+1]=hei[mid+1]; for(int i=mid+2;i<=r;i++) mnr[i]=min(mnr[i-1],hei[i]);
	for(int i=mid+1;i<=r;i++) p[i]=i;
	sort(p+mid+1,p+r+1,comp);
	vector<node> qq; 
	for(int i=l;i<=mid;i++)
		for(pair<int,int> x:q[i])
			qq.push_back((node){sa[i],x.second,x.first});
	if(qq.empty()) return;
	sort(qq.begin(),qq.end(),cmpp);
	int pp=mid+1;
	for(node now:qq){
		while(pp<=r&&sa[p[pp]]+mnr[p[pp]]-1>=now.r){
			add(sa[p[pp]],1);
			pp++;
		}
		ans[now.id]+=query(now.r)-query(max(now.pos,now.r-mnl[rk[now.pos]]+1)-1);//
	}
	for(int i=pp-1;i>mid;i--)
		add(sa[p[i]],-1);
	return;
}
void clr(){
	for(int i=1;i<=cntnode;i++) tr[i].val=tr[i].ln=tr[i].rn=0; cntnode=0;
	for(int i=1;i<=n;i++) rt[i]=0,q[i].clear();
	for(int i=0;i<=max(27,n);i++) buc[i]=0;
	for(int i=1;i<=n;i++) h[i]=hei[i]=0; 
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>ch[i];
	suffix_array();
	get_height();
	for(int i=1;i<=n;i++)
		build(rt[i],rt[i-1],1,n,sa[i]);
	int l,r,k,lef,lim;
	for(int i=1;i<=m;i++){
		cin>>l>>r>>k;
		ans[i]=query(rt[rk[k]],rt[0],1,n,l,r);
		lef=rk[k]; lim=r-k+1;
		for(int j=L-1;j>=0;j--)
			if(lef-(1<<j)+1>=2&&st[lef-(1<<j)+1][j]>=lim)
				lef-=(1<<j);
		if(k-1>=l)
			ans[i]-=query(rt[rk[k]],rt[lef-1],1,n,l,k-1);
		q[rk[k]].push_back(make_pair(i,r));
	}
	cdq(1,n);
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<'\n';
	clr();
	return;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}