#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e5;
struct SA{
	const static int k=23;
	int x[N],y[N],sa[N],rk[N*2],h[N];
	int f[N][25],o[25],p[N];
	inline void init(char*a,int n){
		f(i,0,n*2)rk[i]=0;
		f(i,1,n)rk[i]=a[i],sa[i]=i;
		for(int k=1;k<n;k*=2){
			f(i,1,n)x[i]=rk[i],y[i]=rk[i+k];
			auto cmp=[&](int a,int b){return x[a]!=x[b]?x[a]<x[b]:y[a]<y[b];};
			sort(sa+1,sa+n+1,cmp);
			int m=rk[sa[1]]=1;
			f(i,2,n)rk[sa[i]]=m+=cmp(sa[i-1],sa[i]);
		}
		int l=0;
		f(i,1,n){
			while(a[i+l]==a[sa[rk[i]-1]+l])++l;
			h[rk[i]]=l;if(l)--l;
		}
		f(i,1,n)f[i][0]=h[i];
		f(i,0,k)o[i]=i?o[i-1]*2:1;
		f(i,0,n)p[i]=i?p[i-1]+(o[p[i-1]+1]<=i):0;
		f(t,1,k)f(i,1,n)if(i+o[t]-1<=n)f[i][t]=min(f[i][t-1],f[i+o[t-1]][t-1]);
	}
	inline int ask(int l,int r){int t=p[r-l+1];return min(f[l][t],f[r-o[t]+1][t]);}
	inline int lcp(int x,int y){return x==y?N:ask(min(x,y)+1,max(x,y));}
	inline void lr(int x,int k,int&pl,int&pr){
		x=rk[x];
		int le=1,ri=x,mid;
		while(le<ri){
			mid=(le+ri)/2;
			if(lcp(mid,x)<k)le=mid+1;
			else ri=mid;
		}pl=le;
		le=x;ri=n;
		while(le<ri){
			mid=(le+ri+1)/2;
			if(lcp(x,mid)<k)ri=mid-1;
			else le=mid; 
		}pr=ri;
	}
}S;
struct Kazemaru{
	int c[N],n;
	inline void init(int x){f(i,0,x)c[i]=0;n=x;}
	inline void add(int x,int y){for(;x<=n;x+=-x&x)c[x]+=y;}
	inline int sum(int x,int y=0){for(;x;x-=-x&x)y+=c[x];return y;}
}T;
char a[N];int b[N];
struct op{int l,r,t,p;}L[N],R[N];
vector<op>q[N],o[N];
inline bool operator<(op a,op b){return a.r>b.r;}
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);
	//k<i<=r rk[i]>rk[k],lcp>=r-i+1
	//max(k,r-lcp(k,mid))<i<=r -> L[k].l<R[i].p<=L[k].r;
	//r<i+lcp(mid,i) ->L[k].r<R[i].r
	int cl=0,cr=0,p=0;
	f(i,l,mid){
		int k=S.sa[i];
		for(op e:o[i])L[++cl]=(op){max(k,e.r-S.lcp(i,mid)),e.r,0,e.p};
	}
	f(i,mid+1,r)R[++cr]=(op){0,S.sa[i]+S.lcp(mid,i),0,S.sa[i]};
	sort(L+1,L+cl+1);sort(R+1,R+cr+1);
	f(i,1,cl){
		while(p<cr&&L[i].r<R[p+1].r)T.add(R[++p].p,1);
		b[L[i].p]+=T.sum(L[i].r)-T.sum(L[i].l);
	}
	f(i,1,p)T.add(R[i].p,-1);
}
inline void doing(){
	cin>>n>>m;
	scanf("%s",a+1);
	int r,k,p,pl,pr;
	S.init(a,n);T.init(n);
	f(i,1,n)q[i].clear(),o[i].clear();
	// f(i,1,n)cout<<S.rk[i]<<" ";cout<<endl;
	f(i,1,m){
		cin>>l>>r>>k;b[i]=1;p=S.rk[k]-1;
		//l<=i<k rk[i]<rk[k],lcp<r-k+1
		S.lr(k,r-k+1,pl,pr);pr=min(pr,p);
		q[l-1].push_back({1,p,-1,i});
		q[k-1].push_back({1,p,1,i});
		q[l-1].push_back({pl,pr,1,i});
		q[k-1].push_back({pl,pr,-1,i});
		//k<i<=r rk[i]<rk[k]
		q[k].push_back({1,p-1,-1,i});
		q[r].push_back({1,p-1,1,i});
		//k<i<=r rk[i]>rk[k],lcp>=r-i+1
		if(k<r)o[p+1].push_back({0,r,0,i});
	}
	f(i,1,n){
		T.add(S.rk[i],1);
		for(op e:q[i])b[e.p]+=e.t*(T.sum(e.r)-T.sum(e.l-1));
	}
	T.init(n);cdq(1,n);
	f(i,1,m)printf("%lld\n",b[i]);
}
signed main(){
	int t;
	cin>>t;
	while(t--)doing();
	return 0;
}