#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];
    int preN;
    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,preN);
    	memset(rk,0,preN);
    	memset(height,0,preN);
    	memset(sa,0,preN);
        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;
        }
        preN=max(l,m)+1<<4;
    }
};
struct LCP_SA
{
	struct Word_RMQ
	{
		#define w 32
		#define u unsigned
		#define be(x) ((x>>5)+1)
		#define bm mxn/w+5
		int *a;
		int ST[int(log2(bm)+1)][bm];
		int lg[bm];
		int l[bm],r[bm];
		struct node
		{
			u st[w+1];
			int *p;
			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;
			int i,j,cnt=0,mn;
			for(i=0;i<=n;i+=w)
				l[++cnt]=i,r[cnt]=min(n,i+w-1);
			l[1]=1;
			for(i=1;i<=cnt;i++)
			{
				k[i].init(a+l[i]-1,r[i]-l[i]+1);
				mn=INT_MAX;
				for(j=l[i];j<=r[i];j++)
					mn=min(mn,a[j]);
				ST[0][i]=mn;
			}
			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))]);
			for(i=2;i<=cnt;i++)
				lg[i]=lg[i>>1]+1;
		}
		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]);
		}
		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),ask(L,r[be(L)]),ask(l[be(R)],R)});
		}
	}ds;
	SA a;
	int L;
	void build(char s[],int l,int m)
	{
		a.build(s,l,m);
		ds.build(a.height,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
*/