#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<random>
#include<complex>
#include<cstdlib>
#include<climits>
#include<iomanip>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21],*p1=buf,*p2=buf;
const long long _base=107374183;
int writetemp[30];
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;
    return x;
}
inline void write(int x)
{
	int tot=(x==0);
    writetemp[1]=0;
	while(x) writetemp[++tot]=x%10,x/=10;
    while(tot) putchar(writetemp[tot--]+'0');
    putchar('\n');
	return ;
}
int T;
int n,m,maxx,tot=26,tot1;
char s[1000010];
int rk[1000010],sa[1000010],height[1000010];
int temp[2000010],num[1000010];
int ans[1000010];
struct data_structrue
{
    const int maxx=(1<<20);
    int premin[2000010],sufmin[2000010];
    void init()
    {
        memset(premin,0x3f,(n+1)<<2);
        memset(sufmin,0x3f,(n+1)<<2);
        return ;
    }
    void change(int x,int val)
    {
        int now=x;
        while(x<=maxx) premin[x]=min(premin[x],val),x+=x&-x;
        now=maxx-x+1;
        while(x<=maxx) sufmin[x]=min(sufmin[x],val),x+=x&-x;
        return ;
    }
    int query(int l,int r)
    {
        l++;
        int ans=0x3f3f3f3f;
        while(l<=r&&l-1<=r-(r&-r)) ans=min(ans,premin[r]),r-=r&-r;
        if(l>r) return ans;
        l=maxx-l+1,r=maxx-r+1,swap(l,r);
        while(l<=r&&l-1<=r-(r&-r)) ans=min(ans,sufmin[r]),r-=r&-r;
        return ans;
    }
}tree;
struct BIT
{
    int viscnt;
    int sum[1000010];
    int vis[1000010];
    void clear()
    {
        viscnt++;
        return ;
    }
    void init()
    {
        viscnt=0;
        memset(sum,0,(n+1)<<2);
        memset(vis,0,(n+1)<<2);
        return ;
    }
    void add(int x,int val)
    {
        int temp=x;
        if(x==0)
        {
            if(vis[x]!=viscnt) vis[x]=viscnt,sum[x]=0;
            sum[x]+=val,x=1;
            // printf("x:%d\n",x);
        }
        while(x<=n)
        {
            // printf("add:%d\n",x);
            // if(x==0) printf("%d\n",temp);
            if(vis[x]!=viscnt) vis[x]=viscnt,sum[x]=0;
            sum[x]+=val,x+=x&-x;
        }
        return ;
    }
    int query(int x)
    {
        int ans=0;
        if(x>n) x=n;
        if(x<0) return 0;
        if(x==0)
        {
            if(vis[x]!=viscnt) vis[x]=viscnt,sum[x]=0;
            return sum[x];
        }
        while(x)
        {
            // printf("query:%d\n",x);
            if(vis[x]!=viscnt) vis[x]=viscnt,sum[x]=0;
            ans+=sum[x],x-=x&-x;
        }
        return ans;
    }
}t;
struct que
{
    int x,k,val,id;
}q[1000010],nowq[1000010];
struct Que
{
    int l,r,id;
};
struct HLX
{
    int x,y,id;
};
vector<Que> g[1000010];
bool cmp(que a,que b)
{
    if(a.x==b.x) return a.id<b.id;
    return a.x<b.x;
}
// (qr-i+1<=lcp(rk[k],rk[i])&&rk[k]<rk[i])
// qr+1<=min(nowval[k],nowval[i])+i
int nowval[1000010];
void solve(int l,int r)
{
    if(l==r) return ;
    // printf("%d %d\n",l,r);
    int mid=(l+r)>>1;
    nowval[mid]=0x3f3f3f3f,nowval[mid+1]=height[mid+1];
    for(int i=mid+2;i<=r;i++) nowval[i]=min(nowval[i-1],height[i]);
    for(int i=mid-1;i>=l;i--) nowval[i]=min(nowval[i+1],height[i+1]);
    // nowval[k]<=nowval[i]
    // qr+1-nowval[k]<=i
    tot=0;
    for(int i=l;i<mid;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            int l=max(g[i][j].r+1-nowval[i],g[i][j].l),r=g[i][j].r;
            if(l>r) continue;
            nowq[++tot]=(que){r,nowval[i],1,g[i][j].id};
            nowq[++tot]=(que){l-1,nowval[i],-1,g[i][j].id};
        }
    }
    for(int i=mid+1;i<=r;i++) nowq[++tot]=(que){sa[i],nowval[i],0,0};
    sort(nowq+1,nowq+tot+1,cmp);
    t.clear();
    // printf("start query\n");
    for(int i=1;i<=tot;i++)
    {
        // printf("%d\n",nowq[i].k);
        if(nowq[i].id) ans[nowq[i].id]+=nowq[i].val*t.query(n-nowq[i].k+1);
        else t.add(n-nowq[i].k+1,1);
    }
    // printf("end min=k\n");
    // printf("ans:%d\n",ans[1]);
    // nowval[i]<=nowval[k]-1
    // sa[i]<=qr 1
    // nowval[i]<=nowval[k]-1
    // sa[i]<=ql-1 -1
    tot=0;
    for(int i=l;i<=mid;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            if(nowval[i]-1+g[i][j].r>g[i][j].r) nowq[++tot]=(que){g[i][j].r,nowval[i]-1,1,g[i][j].id};
            if(nowval[i]-2+g[i][j].l>g[i][j].r) nowq[++tot]=(que){g[i][j].l-1,nowval[i]-1,-1,g[i][j].id};
        }
    }
    for(int i=mid+1;i<=r;i++) nowq[++tot]=(que){sa[i],nowval[i],0,0};
    sort(nowq+1,nowq+tot+1,cmp);
    t.clear();
    // printf("start query\n");
    for(int i=1;i<=tot;i++)
    {
        // printf("%d %d\n",nowq[i].k,nowq[i].id);
        if(nowq[i].id) ans[nowq[i].id]+=nowq[i].val*t.query(nowq[i].k);
        else t.add(nowq[i].k,1);
    }
    // printf("end martix\n");
    // printf("ans:%d\n",ans[1]);
    // sa[i]+nowval[i]<=qr
    // nowval[k]<=nowval[i] 1
    
    // sa[i]+nowval[i]<=qr
    // nowval[k]<=nowval[i] -1
    t.clear();
    for(int i=mid;i<=r;i++) t.add(sa[i]+nowval[i],1);
    tot=0;
    for(int i=l;i<=mid;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            if(nowval[i]-1+g[i][j].r>g[i][j].r)
            {
                nowq[++tot]=(que){g[i][j].r,nowval[i],1,g[i][j].id};
                ans[g[i][j].id]-=t.query(g[i][j].r);
            }
            if(nowval[i]-2+g[i][j].l>g[i][j].r)
            {
                nowq[++tot]=(que){g[i][j].r,nowval[i],-1,g[i][j].id};
                ans[g[i][j].id]+=t.query(g[i][j].r);
            }
        }
    }
    for(int i=mid+1;i<=r;i++) nowq[++tot]=(que){sa[i]+nowval[i],nowval[i],0,0};
    sort(nowq+1,nowq+tot+1,cmp);
    t.clear();
    for(int i=1;i<=tot;i++)
    {
        if(nowq[i].id) ans[nowq[i].id]+=nowq[i].val*t.query(n-nowq[i].k+1);
        else t.add(n-nowq[i].k+1,1);
    }
    // printf("end triangle rightdown\n");
    // printf("ans:%d\n",ans[1]);
    // sa[i]+nowval[i]<=qr
    // qr+1<=sa[i] 1

    // sa[i]+nowval[i]<=qr
    // ql<=sa[i] -1
    tot=0;
    for(int i=l;i<=mid;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            if(nowval[i]-1+g[i][j].r>g[i][j].r) nowq[++tot]=(que){g[i][j].r,g[i][j].r+1,1,g[i][j].id};
            if(nowval[i]-2+g[i][j].l>g[i][j].r) nowq[++tot]=(que){g[i][j].r,g[i][j].l,-1,g[i][j].id};
        }
    }
    for(int i=mid+1;i<=r;i++) nowq[++tot]=(que){sa[i]+nowval[i],sa[i],0,0};
    sort(nowq+1,nowq+tot+1,cmp);
    t.clear();
    for(int i=1;i<=tot;i++)
    {
        if(nowq[i].id) ans[nowq[i].id]+=nowq[i].val*t.query(n-nowq[i].k+1);
        else t.add(n-nowq[i].k+1,1);
    }
    // printf("end triangle leftup\n");
    // printf("ans:%d\n",ans[1]);
    solve(l,mid),solve(mid+1,r);
    return ;
}
int main()
{
    // freopen("s.out","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=n;i++) rk[i]=s[i]-'a'+1;
        maxx=tot=26;
        for(int i=1;i<=n;i++) num[rk[i]]++;
        for(int i=1;i<=maxx;i++) num[i]+=num[i-1];
        for(int i=1;i<=n;i++) sa[num[rk[i]]--]=i;
        memset(num,0,(maxx+1)<<2);
        for(int len=1;len<=n;len<<=1)
        {
            maxx=tot,tot=0;
            for(int i=1;i<=n;i++) num[rk[i]]++;
            for(int i=1;i<=maxx;i++) num[i]+=num[i-1];
            for(int i=n+1;i-len<=n;i++) temp[++tot]=i-len;
            for(int i=1;i<=n;i++) if(len<sa[i]) temp[++tot]=sa[i]-len;
            for(int i=n;i>=1;i--) sa[num[rk[temp[i]]]--]=temp[i],temp[i]=rk[i];
            memset(num,0,(maxx+1)<<2);
            tot=rk[sa[1]]=1;
            for(int i=2;i<=n;i++) if(temp[sa[i]]==temp[sa[i-1]]&&temp[sa[i]+len]==temp[sa[i-1]+len]) rk[sa[i]]=tot; else rk[sa[i]]=++tot;
            if(tot==n) break;
        }
        int now=0;
        for(int i=1;i<=n;i++)
        {
            if(now) now--;
            int lst=sa[rk[i]-1];
            while(i+now<=n&&lst+now<=n&&s[i+now]==s[lst+now]) now++;
            height[rk[i]]=now;
        }
        // printf("get_sa end\n");
        // for(int i=1;i<=n;i++) printf("%d ",height[i]);
        tree.init(),tot=0,tot1=0;
        for(int i=1;i<=n;i++) tree.change(i,height[i]);
        for(int i=1;i<=m;i++)
        {
            int ql,qr,k;
            scanf("%d%d%d",&ql,&qr,&k);
            // i\in[ql,k-1],lcp(rk[i],rk[k])<qr-k+1&&rk[i]<rk[k]
            if(ql<=k-1)
            {
                int l=0,r=rk[k];
                while(l<r)
                {
                    int mid=l+r+1>>1;
                    if(tree.query(mid,rk[k])<qr-k+1) l=mid;
                    else r=mid-1;
                }
                q[++tot]=(que){k-1,l,1,i};
                if(ql>1) q[++tot]=(que){ql-1,l,-1,i};
            }
            // i\in[k+1,qr],rk[i]<rk[k]||(qr-i+1<=lcp(rk[k],rk[i])&&rk[k]<rk[i])
            if(k+1<=qr)
            {
                q[++tot]=(que){qr,rk[k]-1,1,i};
                q[++tot]=(que){k,rk[k]-1,-1,i};
                g[rk[k]].push_back((Que){k+1,qr,i});
            }
            ans[i]=0;
        }
        // printf("get_query end\n");
        sort(q+1,q+tot+1,cmp);
        now=1,t.init();
        for(int i=1;i<=n;i++)
        {
            // if(rk[i]<0) printf("%d\n",i);
            t.add(rk[i],1);
            while(now<=tot&&q[now].x==i) ans[q[now].id]+=q[now].val*t.query(q[now].k),now++;
        }
        // printf("query end\n");
        // printf("ans:%d\n",ans[1]);
        solve(1,n);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]+1);
    }
    cerr<<(int)clock()<<'\n';
    return 0;
}
/*
0 0 0 0 0 0
1 1 1 0 0 0
1 1 1 1 0 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0

1
20 1
cccbccbadaacbbbcccab
14 17 16
*/