#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=5e4+4;
int n,m,sa[N],rk[N],h[N];
char S[N];
inline void make(){
	static int old[N],cnt[N],id[N];
	int m=26;
	rep(i,1,n)++cnt[rk[i]=S[i]-'a'+1];
	rep(i,1,m)cnt[i]+=cnt[i-1];
	per(i,n,1)sa[cnt[rk[i]]--]=i;
	rep(i,1,m)cnt[i]=0;
	for(int w=1,p;;w<<=1,m=p){
		p=0;
		rep(i,n-w+1,n)id[++p]=i;
		rep(i,1,n)if(sa[i]>w)id[++p]=sa[i]-w;
		rep(i,1,n)++cnt[rk[i]];
		rep(i,1,m)cnt[i]+=cnt[i-1];
		per(i,n,1)sa[cnt[rk[id[i]]]--]=id[i],id[i]=0;
		rep(i,1,m)cnt[i]=0;
		swap(rk,old);p=0;
		rep(i,1,n)rk[sa[i]]=(old[sa[i]]==old[sa[i-1]]&&old[sa[i]+w]==old[sa[i-1]+w])?p:++p;
		if(p==n)break;
	}
	rep(i,2,n){
		int &k=h[rk[i]]=max(0,h[rk[i-1]]-1);
		while(S[i+k]==S[sa[rk[i]-1]+k])++k;
	}
}
struct Node{ int l,r,k,id;};
int ans[N];
#define lb(x) (x&-x)
int t[N];
inline void ad(int x,int k){for(;x<=n;x+=lb(x))t[x]+=k;}
inline int qr(int l,int r){
	if(l>r)return 0;
	int res=0; 
	for(;r>0;r-=lb(r))res+=t[r];
	for(--l;l>0;l-=lb(l))res-=t[l];
	return res;
}
int s[N];
inline void solve(int l,int r,vector<Node>&vec){
	if(l==r)return;
	vector<Node>v1,v2;int m=(l+r)>>1;
	for(auto tmp:vec){
		if(rk[tmp.k]<=m)v1.pb(tmp);
		else v2.pb(tmp);
	}
	solve(l,m,v1),solve(m+1,r,v2);
	s[m]=INT_MAX; per(i,m-1,l)s[i]=min(s[i+1],h[i+1]);
	s[m+1]=h[m+1];rep(i,m+2,r)s[i]=min(s[i-1],h[i]);
	static int id[N];rep(i,l,r)id[i]=i;
	sort(v1.begin(),v1.end(),[](Node A,Node B){return A.r>B.r;});
	sort(id+m+1,id+r+1,[&](int i,int j){return s[i]+sa[i]>s[j]+sa[j];});
	int j=m+1;
	for(auto tmp:v1){
		while(j<=r && s[id[j]]+sa[id[j]]>=tmp.r+1)ad(n-sa[id[j++]]+1,1);
		ans[tmp.id]+=qr(n-tmp.r+1,n-max(max(tmp.l,tmp.k),tmp.r-s[rk[tmp.k]]+1)+1);
	}
	rep(jj,m+1,j-1)ad(n-sa[id[jj]]+1,-1);
	sort(v2.begin(),v2.end(),[](Node A,Node B){return A.r-A.k<B.r-B.k;});
	sort(id+l,id+m+1,[&](int i,int j){return s[i]<s[j];});
	int i=l;
	for(auto tmp:v2)if(s[rk[tmp.k]]>=tmp.r-tmp.k+1){
		while(i<=m && s[id[i]]<tmp.r-tmp.k+1)ad(sa[id[i++]],1);
		ans[tmp.id]+=qr(tmp.l,tmp.k);
	}
	while(i<=m)ad(sa[id[i++]],1);
	for(auto tmp:v2){
		if(s[rk[tmp.k]]<tmp.r-tmp.k+1)ans[tmp.id]+=qr(tmp.l,tmp.r);
		else ans[tmp.id]+=qr(tmp.k,tmp.r);
	}
	rep(i,l,m)ad(sa[i],-1);
}
inline void solve(){
	n=read(),m=read(); scanf("%s",S+1); make();
	vector<Node>vec(m);
	rep(i,0,m-1)vec[i].l=read(),vec[i].r=read(),vec[i].k=read(),vec[i].id=i+1;
	solve(1,n,vec);
	rep(i,1,m)printf("%d\n",ans[i]+1),ans[i]=0;
}
int main() {
    //freopen("data.in", "r", stdin);
    //freopen("myans.out","w",stdout);
	int T=read();while(T--)solve();
    return 0;
}