#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) h[i]=0,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){
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;
}
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;
}