#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long
using namespace std;
const int N=5e4+5;
int n,q;char s[N];
tuple<int,int,int>A[N*2];
vector<tuple<int,int,int>>Q[N],nQ[N];
int sa[N],rk[N],height[N],ans[N],T[N*4];
struct FenwickTree{
    int n,c[N];
    inline void build(const int&_n){n=_n,fill(c+1,c+n+1,0);}
    inline void add(int x,const int&y){for(;x<=n;x+=x&-x)c[x]+=y;}
    inline int sum(int x,int z=0){for(;x;x-=x&-x)z+=c[x];return z;}
}T0;
inline void SA(char *s,int n){
	static int t1[N],t2[N],cnt[N];
	int *x=t1,*y=t2,m=127;
	for(int i=1;i<=n;++i)++cnt[x[i]=s[i]];
	for(int i=2;i<=m;++i)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;--i)sa[cnt[x[i]]--]=i;
	fill(cnt+1,cnt+m+1,0);
	for(int k=1;;k<<=1){
		int p=0;
		for(int i=n-k+1;i<=n;++i)y[++p]=i;
		for(int i=1;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;
		for(int i=1;i<=n;++i)++cnt[x[i]];
		for(int i=2;i<=m;++i)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;--i)sa[cnt[x[y[i]]]--]=y[i],y[i]=0;
		fill(cnt+1,cnt+m+1,0);
		swap(x,y),x[sa[p=1]]=1;
		for(int i=2;i<=n;++i)
			x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]);
		if((m=p)>=n)break;
	}
	for(int i=1;i<=n;++i)rk[sa[i]]=i;
	for(int i=1,j=0;i<=n;++i){
		j=max(j-1,0);
		if(rk[i]==1)continue;
		int k=sa[rk[i]-1];
		while(i+j<=n&&j+k<=n&&s[i+j]==s[j+k])++j;
		height[rk[i]]=j;
	}
}
inline void build(int p,int l,int r){
    if(l==r)return T[p]=height[l],void();
    const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
    build(ls,l,mid),build(rs,mid+1,r);
    T[p]=min(T[ls],T[rs]);
}
inline int qry(int p,int l,int r,int x,int y){
    if(T[p]>y)return l-1;
    if(l==r)return l;
    const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
    const int z=(x>mid?qry(rs,mid+1,r,x,y):mid);
    return z<=mid?qry(ls,l,mid,x,y):z;
}
inline void solve(int l,int r){
    if(l>=r){
        nQ[l].clear();
        return;
    }
    const int p=(l+r)>>1;
    int m=0;
    for(int i=p+1,c=height[i];i<=r;++i)
        c=min(height[i],c),T0.add(sa[i],1),
        A[++m]=make_tuple(sa[i]+c,0,sa[i]);
    for(int i=p,c=height[i+1];i>=l;--i){
        c=min(c,height[i+1]);
        for(auto [k,r,id]:nQ[i])
            ans[id]+=T0.sum(r)-T0.sum(max(r-c,k)),
            A[++m]=make_tuple(r,id,max(r-c,k)+1);
    }
    for(int i=p+1;i<=r;++i)T0.add(sa[i],-1);
    sort(A+1,A+m+1);
    for(int i=1;i<=m;++i)
        if(get<1>(A[i]))ans[get<1>(A[i])]-=T0.sum(n-get<2>(A[i])+1);
        else T0.add(n-get<2>(A[i])+1,1);
    for(int i=1;i<=m;++i)if(!get<1>(A[i]))T0.add(n-get<2>(A[i])+1,-1);
    solve(l,p),solve(p+1,r);
}
int qc=0;
inline void MAIN(){
    cin>>n>>q>>(s+1);
    SA(s,n),build(1,1,n);
    for(int i=1;i<=q;++i){
        int l,r,k;cin>>l>>r>>k,ans[i]=1;
        if(k<r)
            Q[rk[k]].emplace_back(k+1,r,i),
            nQ[rk[k]].emplace_back(k,r,i);
        if(l<k)Q[qry(1,1,n,rk[k],r-k)-1].emplace_back(l,k-1,i);
        if((++qc)==38){
            cout<<(s+1)<<endl;
            for(int i=1;i<=n;++i)cout<<sa[i]<<" "<<height[i]<<endl;
        }
    }
    T0.build(n);
    for(int i=1;i<=n;++i){
        T0.add(sa[i],1);
        for(auto [l,r,id]:Q[i])ans[id]+=T0.sum(r)-T0.sum(l-1);
        Q[i].clear();
    }
    T0.build(n),solve(1,n);
    for(int i=1;i<=q;++i)cout<<ans[i]<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t=1;cin>>t;while(t--)MAIN();
    return 0;
}
/*
*/