#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<int,int>
template <class Miaowu>
inline void in(Miaowu &x){
    char c;x=0;bool f=0;
    for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
mt19937 rnd(time(NULL));
const int N=5e4+5;
char a[N];
int T,n,m,lg[N],rd[26];
struct ES{int sx,mx,gx;};
struct Border{
    char a[N];
    int n,lst[N*20],llst[N*20],cnt[N*20],bh[N][20],id[N][20];
    struct Hash{
        int B,mod,val,len,P[N];
        inline void add(char c){val=(1ll*val*B+rd[c-'a'])%mod,len++;}
        inline void del(char c){val=(val+mod-1ll*rd[c-'a']*P[len-1]%mod)%mod,len--;}
    }H1,H2;
    struct Hashid{
        int ind,tot,head[1<<20],top,stk[1<<20];
        struct E{int nxt,qaq;ll val;}e[N*20];
        inline int ins(int x,int y){
            ll num=1ll*x*(ll)(1e9+9)+y,dy=(num>>40ll);
            for(int i=head[dy];i;i=e[i].nxt)if(e[i].val==num)return e[i].qaq;
            if(!head[dy])stk[++top]=dy;
            e[++tot]=E{head[dy],(++ind),num},head[dy]=tot;
            return ind;
        }
    }hsh;
    struct HashES{
        unordered_map<int,ES>mp;
        inline void ins(int x,ES y){mp[x]=y;}
        inline ES qry(int x){return mp[x];}
    }vh[N<<2];
    inline Border(){
        for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;
        for(int i=0,j=1;i<26;i++){
            int k=j+rnd()%9983+1;
            rd[i]=1ll*rnd()%(k-j+1)*rnd()%(k-j+1)+j,j=k+1;
        }
    }
    inline void clear(int n){
        for(int i=1;i<=hsh.top;i++)hsh.head[hsh.stk[i]]=0;
        for(int i=0;i<(n<<2);i++)vh[i].mp.clear();
        hsh.ind=hsh.tot=hsh.top=0;
    }
    inline void init(){
        n=::n;int bhh=0;
        for(int i=1;i<=n;i++)a[i]=::a[i];
        for(int b=0;(1<<b)<=n;b++){
            for(int i=1;(i-1)*(1<<b)+1<=n;i++)bh[i][b]=++bhh;
        }
        H1.B=999983,H1.mod=1e9+7,H2.B=19260817,H2.mod=1e9+9;
        for(int i=H1.P[0]=H2.P[0]=1;i<N;i++)H1.P[i]=1ll*H1.P[i-1]*H1.B%H1.mod,H2.P[i]=1ll*H2.P[i-1]*H2.B%H2.mod;
        for(int b=1,bb=0;b<=n;b<<=1,bb++){
            for(int st=1;st<=n;st+=b){
                H1.val=H2.val=H1.len=H2.len=0;
                for(int i=st;i<=st+b-1;i++)H1.add(a[i]),H2.add(a[i]);
                vector<int>vc;
                for(int i=st;i<=st+b-1&&i+b-1<=n;i++){
                    id[i][bb]=hsh.ins(H1.val,H2.val),vc.push_back(id[i][bb]);
                    llst[id[i][bb]]=lst[id[i][bb]],lst[id[i][bb]]=i,cnt[id[i][bb]]++;
                    if(st+b<=n)H1.del(a[i]),H1.add(a[i+b]),H2.del(a[i]),H2.add(a[i+b]);
                }
                for(int i=vc.size()-1;i>=0;i--){
                    cnt[vc[i]]--;
                    if(cnt[vc[i]]==0)vh[bh[(st-1)/b+1][bb]].ins(vc[i],ES{i+st,lst[vc[i]],((!llst[vc[i]])?0:(lst[vc[i]]-llst[vc[i]]))});
                }
                for(int x:vc)lst[x]=llst[x]=0;
            }
        }
    }
    inline ES upd(ES qwq,int lp,int rp){
        if(qwq.gx==-1)return qwq;
        if(qwq.mx<lp||qwq.sx>rp)return ES{-1,-1,-1};
        if(qwq.gx==0)return qwq.sx>=lp&&qwq.mx<=rp?qwq:ES{-1,-1,-1};
        if(qwq.sx<lp){
            int tt=(lp-qwq.sx-1)/qwq.gx+1;qwq.sx+=tt*qwq.gx;
        }
        if(qwq.mx>rp){
            int tt=(qwq.mx-rp-1)/qwq.gx+1;qwq.mx-=tt*qwq.gx;
        }
        if(qwq.sx>qwq.mx)return ES{-1,-1,-1};
        if(qwq.sx==qwq.mx)qwq.gx=0;
        return qwq;
    }
    inline ES match(int l,int b,int lp,int rp){
        int bl=(lp-1)/(1<<b)+1;rp=rp-(1<<b)+1;
        if(bl==(rp-1)/(1<<b)+1)return upd(vh[bh[bl][b]].qry(id[l][b]),lp,rp);
        ES qwq1=upd(vh[bh[bl][b]].qry(id[l][b]),lp,rp),qwq2=upd(vh[bh[bl+1][b]].qry(id[l][b]),lp,rp);
        if(qwq1.gx==-1)return qwq2;
        if(qwq2.gx==-1)return qwq1;
        int tt=max(qwq1.gx,qwq2.gx);
        return ES{qwq1.sx,qwq2.mx,(tt==0?(qwq2.mx-qwq1.sx):tt)};
    }
    inline bool have(ES x,int num){
        if(x.gx==0)return num==x.sx;
        return num>=x.sx&&num<=x.mx&&(num-x.sx)%x.gx==0;
    }
    inline vector<ES> qry(int l,int r){
        vector<ES>res;if(l==r)return res;
        for(int i=0;i<=lg[r-l];i++){
            int len=min(r-l,(1<<i+1)-1);
            ES qwq1=match(l,i,r-len+1,r),qwq2=match(r-(1<<i)+1,i,l,l+len-1);
            if(qwq1.gx==-1||qwq2.gx==-1)continue;
            qwq2.sx+=(1<<i)-l,qwq2.mx+=(1<<i)-l;
            swap(qwq1.sx,qwq1.mx),qwq1.sx=r+1-qwq1.sx,qwq1.mx=r+1-qwq1.mx;
            int xs1=(qwq1.gx==0?1:((qwq1.mx-qwq1.sx)/qwq1.gx+1));
            int xs2=(qwq2.gx==0?1:((qwq2.mx-qwq2.sx)/qwq2.gx+1));
            if(min(xs1,xs2)<3){
                if(xs1>xs2)swap(qwq1,qwq2);
                if(qwq1.gx==0){
                    if(have(qwq2,qwq1.sx))res.push_back(qwq1);
                }
                else{
                    bool f1=have(qwq2,qwq1.sx),f2=have(qwq2,qwq1.mx);
                    if(f1&&f2)res.push_back(qwq1);
                    else if(f1)res.push_back(ES{qwq1.sx,qwq1.sx,0});
                    else if(f2)res.push_back(ES{qwq1.mx,qwq1.mx,0});
                }
            }
            else{
                if(abs(qwq1.sx-qwq2.sx)%qwq1.gx!=0)continue;
                int sx=max(qwq1.sx,qwq2.sx),mx=min(qwq1.mx,qwq2.mx);
                if(sx>mx)continue;
                if(sx==mx)res.push_back(ES{sx,mx,0});
                else res.push_back(ES{sx,mx,qwq1.gx});
            }
        }
        return res;
    }
}miao;
int sa[N],rk[N],cnt[N],key1[N],osa[N],ork[N],ht[N][20],ans[N];
inline void init(){
    a[n+1]='!';int lim=127;
    for(int i=1;i<=n;i++)cnt[rk[i]=a[i]]++;
    for(int i=1;i<=lim;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
    for(int i=1;i<=lim;i++)cnt[i]=0;
    for(int w=1,p=0;;w<<=1,lim=p,p=0){
        for(int i=n;i>n-w;i--)osa[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>w)osa[++p]=sa[i]-w;
        for(int i=1;i<=n;i++)cnt[key1[i]=rk[osa[i]]]++;
        for(int i=1;i<=lim;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[key1[i]]--]=osa[i];
        for(int i=1;i<=lim;i++)cnt[i]=0;
        for(int i=1;i<=n;i++)ork[i]=rk[i];p=0;
        for(int i=1;i<=n;i++)
            rk[sa[i]]=(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+w]==ork[sa[i-1]+w]?p:(++p));
        if(p==n)break;
    }
    for(int i=1,j=0;i<=n;i++){
        if(j)j--;
        while(max(i,sa[rk[i]-1])+j<=n&&a[i+j]==a[sa[rk[i]-1]+j])j++;
        ht[rk[i]][0]=j;
    }
    for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
        ht[i][j]=min(ht[i][j-1],ht[i+(1<<j-1)][j-1]);
}
inline int getlcp(int l,int r){
    int k=lg[r-(l++)];
    return min(ht[l][k],ht[r-(1<<k)+1][k]);
}
struct Qry{int l,r,id;};
vector<Qry>Q[N];
struct BIT{
    int tree[N];
    inline void upd(int u,int x){
        for(;u<=n;u+=u&-u)tree[u]+=x;
    }
    inline int qry(int u){
        int res=0;
        for(;u;u-=u&-u)res+=tree[u];
        return res;
    }
}bit;
int main(){
    for(cin>>T;T;T--){
        in(n),in(m),scanf("%s",a+1),miao.init(),init();
        for(int i=0;i<=n;i++)Q[i].clear(),bit.tree[i]=0;
        for(int i=1,l,r,k;i<=m;i++){
            in(l),in(r),in(k),ans[i]=0;
            if(k<r)Q[rk[k]].push_back(Qry{k+1,r,i});
            int lf=1,rt=rk[k]-1,res=0;
            while(lf<=rt){
                int mid=lf+rt>>1;
                if(getlcp(mid,rk[k])<r-k+1)res=mid,lf=mid+1;
                else rt=mid-1;
            }
            if(res&&k>l)Q[res].push_back(Qry{l,k-1,i});
            vector<ES> bd=miao.qry(k,r);
            for(ES x:bd){
                if(x.gx==0){
                    ans[i]+=(rk[r-x.sx+1]>rk[k]);continue;
                }
                swap(x.mx,x.sx),x.sx=r-x.sx+1,x.mx=r-x.mx+1;
                lf=1,rt=(x.mx-x.sx)/x.gx+1,res=-1;
                if(rk[x.sx]<rk[x.mx]){
                    while(lf<=rt){
                        int mid=lf+rt>>1;
                        if(rk[(mid-1)*x.gx+x.sx]>rk[k])res=mid,rt=mid-1;
                        else lf=mid+1;
                    }
                    if(res!=-1)ans[i]+=(x.mx-x.sx)/x.gx+1-res+1;
                }
                else{
                    while(lf<=rt){
                        int mid=lf+rt>>1;
                        if(rk[(mid-1)*x.gx+x.sx]>rk[k])res=mid,lf=mid+1;
                        else rt=mid-1;
                    }
                    if(res!=-1)ans[i]+=res;
                }
            }
        }
        for(int i=1;i<=n;i++){
            bit.upd(sa[i],1);
            for(Qry x:Q[i])ans[x.id]+=bit.qry(x.r)-bit.qry(x.l-1);
        }
        for(int i=1;i<=m;i++)printf("%d\n",ans[i]+1);
        miao.clear(n);
    }
    return 0;
}