#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 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)});
	}
	#undef w
}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);
}
char s[mxn];
int ans[mxn];
int n;
struct bit
{
	#define lowbit(x) (x&-x)
	int t[mxn];
	void add(int x,int v)
	{
		for(;x<=n;x+=lowbit(x))
			t[x]+=v;
	}
	int ask(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			s+=t[x];
		return s;
	}
}T0;
vector<pair<int,pair<int,int>>> qwq[mxn];
int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		memset(T0.t,0,n+1<<2);
		int m=read(),i,j,l,r,k,p;
		scanf("%s",s+1);
		build(s,n,'z');
		for(i=1;i<=n;i++)
			qwq[i].clear();
		for(i=1;i<=m;i++)
		{
			int sum=1,w=0;
			l=read(),r=read(),k=read();
			for(j=1<<20;j;j>>=1)
				w+=(w+j<a.rk[k]&&ds.ask(w+j+1,a.rk[k])<=r-k)*j;
//			sum+=a.rk[k]-w+1;
			qwq[w].push_back({i,{l,k-1}});
//			for(j=1;j<=w;j++)
//				sum+=a.sa[j]>=l&&a.sa[j]<k;
//			for(p=l;p<k;p++)
//				if(asklcp(p,k)<=r-k)
//					sum+=a.rk[p]<a.rk[k];
			for(p=k+1;p<=r;p++)
				if(p+asklcp(p,k)-1<r)
					sum+=a.rk[p]<a.rk[k];
				else sum++;
			ans[i]=sum;
		}
		for(i=1;i<=n;i++)
		{
			T0.add(a.sa[i],1);
			for(auto x:qwq[i])
				ans[x.first]+=T0.ask(x.second.second)-T0.ask(x.second.first-1);
		}
		for(i=1;i<=m;i++)
			printf("%d\n",ans[i]);
	}
}
/*
1
10 10
abaabbaabb
2 8 3

1
10 10
abaabbaabb
2 8 3
*/