#include<bits/stdc++.h>
using namespace std;
const int N=400005,inf=1e9;
int _,T,len,n,q;
int rk[N*2],rnk[N*2],sa[N],now,rkk[N];
int rk1[N],rk0[N],d[N],ans[N],tr[2][N];
int al[2],buc[N],id[N];
vector<int>v[N],vv[N];
char str[N],strr[N],b[N*2];
struct Qry{
	int i,len,o;
}a[N];
int read(){
	char x=getchar();int s=0;
	while (x<48||x>57)x=getchar();
	while (x>=48&&x<=57)s=(s<<1)+(s<<3)+(x^48),x=getchar();
	return s;
}
void add(int tp,int x){if (!x)return;++al[tp];for (int i=x;i<=len;i+=(i&(-i)))++tr[tp][i];}
int qry(int tp,int x){int s=0;for (int i=x;i;i-=(i&(-i)))s+=tr[tp][i];return s;}
//bool cmp(int x,int y){return rk[x]==rk[y]?(rk[x+now]<rk[y+now]):(rk[x]<rk[y]);}
void Sa(){
	int m=1<<8,p=0;
	for (int i=0;i<=len+len;++i)rk[i]=rnk[i]=0;
	for (int i=0;i<=max(len+len,m);++i)buc[i]=0;
	for (int i=1;i<=len;++i)buc[rk[i]=strr[i]]++;
	for (int i=1;i<=m;++i)buc[i]+=buc[i-1];
	for (int i=len;i;--i)sa[buc[rk[i]]--]=i;
	for (int w=1;w<len;m=p,p=0,w<<=1){
		for (int i=len-w+1;i<=len;++i)id[++p]=i;
		for (int i=1;i<=len;++i)if(sa[i]>w)id[++p]=sa[i]-w;
		memset(buc,0,m+1<<2),memcpy(rnk,rk,len+1<<2),p=0;
		for (int i=1;i<=len;++i)++buc[rk[i]];
		for (int i=1;i<=m;++i)buc[i]+=buc[i-1];
		for (int i=len;i;--i)sa[buc[rk[id[i]]]--]=id[i];
		for (int i=1;i<=len;++i)rk[sa[i]]=(rnk[sa[i-1]]==rnk[sa[i]]&&rnk[sa[i-1]+w]==rnk[sa[i]+w]?p:++p); 
		if (p==len)break;
	}
}
void write(int x){
	if (x>9)write(x/10);
	putchar(x%10+48);
}
void solve(){
	n=read(),q=read();
	scanf("%s",str+1);
	for (int i=1;i<=n;++i)strr[i]=strr[n+n-i+1]=str[i];len=n+n;
	Sa();
//	return;
	for (int i=1;i<=n;++i){
		rkk[i]=rk[len-i+1];
		rk1[i]=rk0[i]=0;
		if (i&1)rk1[i]=rkk[i];
		else rk0[i]=rkk[i];
	}
	for (int i=1;i<=q;++i){
		a[i].i=read(),a[i].len=read();
		int L=a[i].i,R=a[i].i+a[i].len*2-1;
		a[i].o=R&1;ans[i]=0;
		v[R].push_back(i);
		vv[L].push_back(i);
	}
	int j=0;al[0]=al[1]=0;
	for (int i=1;i<=n;++i){
		add(1,rk1[i]),add(0,rk0[i]);
		for (int j:v[i])
			ans[j]+=al[a[j].o]-qry(a[j].o,rk[a[j].i]);
		for (int j:vv[i])
			ans[j]-=al[a[j].o]-qry(a[j].o,rk[a[j].i]);
	}
//	return;
	for (int i=1;i<=len;++i)tr[0][i]=tr[1][i]=0,v[i].clear(),vv[i].clear();
	for (int i=1;i<=len;++i)b[i*2]=strr[i];
	for (int i=1;i<=len;++i)b[i*2-1]='#';
	int r=0;j=0;
	for (int i=1;i<=len;++i){
		if (i<r)d[i]=min(r-i,d[j*2-i]);
		else d[i]=1;
		while (b[i+d[i]]==b[i-d[i]]&&i-d[i]>=1&&i+d[i]<=len+len)++d[i];
		if (i+d[i]>r)r=i+d[i],j=i;
	}
	for (int i=2;i<=len;i+=2)d[i]=-inf;
	for (int i=1;i<=len;i+=2)if (i-d[i]==0||b[i-d[i]]<b[i+d[i]])d[i]=-inf;
	for (int i=1;i<=len;++i)d[i]-=i,d[i]+=2*n,d[i]=max(d[i],0);
	for (int i=1;i<=q;++i){
		int L=a[i].i*2,R=a[i].i*2+2*a[i].len-1;
		v[R].push_back(i);
		vv[L].push_back(i);
	}
	j=0;int all=0;
	for (int i=1;i<=len;++i){
		add(0,d[i]);all+=(d[i]!=0);
		for (int j:v[i])ans[j]-=all-qry(0,2*n-a[j].i*2);
		for (int j:vv[i])ans[j]+=all-qry(0,2*n-a[j].i*2);
	}
	for (int i=0;i<=len;++i)tr[0][i]=0,v[i].clear(),vv[i].clear();
	for (int i=1;i<=q;++i)write(ans[i]),putchar(10);
}
int main(){
	_=read(),T=read();
	while (T--)solve();
}