#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=2e5+5;
struct SA
{
    #define f(i,a,b) for(i=a;i<=b;i++)
    #define e(i,a,b) for(i=a;i>=b;i--)
    int sa[mxn],height[mxn];
    int cnt[mxn],rk[mxn];
    void S_sort(char s[],int l,int m)
    {
        int i,k,ct;
        f(i,1,l) cnt[height[i]=s[i]]++;
        f(i,2,m) cnt[i]+=cnt[i-1];
        e(i,l,1) sa[cnt[height[i]]--]=i;
        for(k=1;k<=l;k*=2)
        {
            ct=0;
            f(i,l-k+1,l) rk[++ct]=i;
            f(i,1,l)
                if(sa[i]>k)
                    rk[++ct]=sa[i]-k;
            f(i,1,m) cnt[i]=0;
            f(i,1,l) cnt[height[i]]++;
            f(i,2,m) cnt[i]+=cnt[i-1];
            e(i,l,1) sa[cnt[height[rk[i]]]--]=rk[i],rk[i]=0;
            swap(height,rk);
            height[sa[1]]=m=1;
            f(i,2,l)
                height[sa[i]]=m=m+!(rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+k]==rk[sa[i-1]+k]);
            if(m==l) return;    
        }
    }
    void build(char s[],int l,int m)
    {
    	memset(cnt,0,max(l,m)+1<<3);
        S_sort(s,l,m);    
        int i,j,k;
        for(i=1;i<=l;i++)
            rk[sa[i]]=i;
        for(i=1,k=0;i<=l;i++)
        {
            if(rk[i]==1) k=0;
            else
            {
                k-=k>0;
                int j=sa[rk[i]-1];
                while(i+k<=l&&j+k<=l&&s[i+k]==s[j+k])
                    k++;
            }
            height[rk[i]]=k;
        }
    }
};
struct LCP_SA
{
	struct Word_RMQ
	{
	    #define w 32
	    #define u unsigned
	    #define be(x) ((x>>5)+1)
	    #define l(x) ((x-1<<5)+(x==1))
	    #define r(x) min(N,((x<<5)-1))
	    #define bm mxn/w+5
	    int N,*a;
	    int ST[int(log2(bm)+1)][bm];
	    int pre[mxn],nxt[mxn];
	    struct node
	    {
	        u st[w+1];
	        int *p;
	        inline int ask(int l,int r)
	        {
	            return p[l+__builtin_ctz(st[r]>>l-1)];
	        }
	        void init(int *p_,int len)
	        {
	            p=p_;
	            int i,top=0;
	            int stack[w+1];
	            for(i=1;i<=len;i++)
	            {
	                st[i]=st[i-1];
	                while(top&&p[i]<p[stack[top]])
	                    st[i]-=1u<<stack[top--]-1;
	                stack[++top]=i,st[i]+=1u<<i-1;
	            }
	        }
	    }k[bm];
	    void build(int A[],int n)
	    {
	        a=A,N=n;
	        int i,j,cnt=0;
	        for(i=1;;i++)
	        {
	            k[i].init(a+l(i)-1,r(i)-l(i)+1);
	            for(j=l(i)+1,pre[l(i)]=a[l(i)];j<=r(i);j++)
	            	pre[j]=min(pre[j-1],a[j]);
	            for(j=r(i)-1,nxt[r(i)]=a[r(i)];j>=l(i);j--)
	            	nxt[j]=min(nxt[j+1],a[j]);
	            ST[0][i]=pre[r(i)];
	            cnt++;
	            if(r(i)==n) break;
	        }
	        for(j=1;(1<<j)<=cnt;j++)
	            for(i=1;i+(1<<j)-1<=cnt;i++)
	                ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
	    }
	    inline int STask(int L,int R)
	    {
	        if(L>R) return INT_MAX;
	        int k=__lg(R-L+1);
	        return min(ST[k][L],ST[k][R-(1<<k)+1]);
	    }
	    inline int ask(int L,int R)
	    {
	        if(L>R) return INT_MAX;
	        if(be(L)==be(R)) return k[be(L)].ask(L-l(be(L))+1,R-l(be(L))+1);
	        return min({STask(be(L)+1,be(R)-1),pre[R],nxt[L]});
	    }
	    #undef w
	    #undef l
	    #undef r
	}ds;
	SA a;
	int L;
	void build(char s[],int l,int m)
	{
		a.build(s,l,m);
		ds.build(a.height,l);
      L=l;
	}
	int asklcp(int x,int y)
	{
		if(x==y) return L-x+1;
		x=a.rk[x],y=a.rk[y];
		if(x>y) swap(x,y);
		return ds.ask(x+1,y);
	}
}a;
char s[mxn];
int main()
{
	int T=read();
	while(T--)
	{
		int n=read(),m=read(),i,l,r,k,p;
		scanf("%s",s+1);
		a.build(s,n,'z');
		while(m--)
		{
			int sum=1;
			l=read(),r=read(),k=read();
			for(p=l;p<k;p++)
				if(k+a.asklcp(p,k)-1<r)
					sum+=a.a.rk[p]<a.a.rk[k];
			for(p=k+1;p<=r;p++)
				if(p+a.asklcp(p,k)-1<r)
					sum+=a.a.rk[p]<a.a.rk[k];
				else sum++;
			printf("%d\n",sum);	
		}
	}
}
/*
1
10 10
abaabbaabb
2 8 3

1
10 10
abaabbaabb
2 8 3
*/