#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n,q;
char s[N],ss[N];
int v1[N],v2[N],ton[N],sa[N];
int rk[N];
inline int Rev(int x) { return n + n + 2 - x;}
inline bool cmp(int *r,int i,int j,int k) {
	return r[i] == r[j] && (i + k > n ? 0 : r[i + k]) == (j + k > n ? 0 : r[j + k]);
}
inline void GetSa(char *s,int *sa,int n,int m) {
	#define For(i,a,b) for(int i = (a);i <= (b);i++)
	#define Rof(i,a,b) for(int i = (a);i >= (b);i--) 
	int *x = v1,*y = v2,*t;
	For(i,1,m) ton[i] = 0;
	For(i,1,n) ton[x[i] = s[i]]++;
	For(i,1,m) ton[i] += ton[i - 1];
	Rof(i,n,1) sa[ton[x[i]]--] = i;
	for(int j = 1,p;j <= n;j *= 2,m = p) {
		p = 0;
		For(i,n - j + 1,n) y[++p] = i;
		For(i,1,n) if(sa[i] > j) y[++p] = sa[i] - j;
		For(i,1,m) ton[i] = 0;
		For(i,1,n) ton[x[i]]++;
		For(i,1,m) ton[i] += ton[i - 1];
		Rof(i,n,1) sa[ton[x[y[i]]]--] = y[i],y[i] = 0;
		t = x;x = y;y = t;p = 1;x[sa[1]] = 1;
		For(i,2,n) x[sa[i]] = cmp(y,sa[i - 1],sa[i],j) ? p : (++p);
		if(p >= n) break;
	}
}
int R[N]; // 以 i 为较右回文中心的最长偶回文串
inline void Manacher() {
	int l = 0,r = 0;
	for(int i = 1;i <= n;i++) {
		if(i < r) R[i] = min(R[2 * l - i],r - i); else R[i] = 0;
		while(i + R[i] <= n && i - 1 - R[i] > 0 && s[i + R[i]] == s[i - 1 - R[i]])
			++R[i];
		if(i + R[i] > r) l = i,r = i + R[i];
	}
}
int ans[N];
struct BIT {
	int tr[N];
	#define lowbit(x) (x&(-x))
	inline void Clr() { for(int i = 0;i <= n + n + 2;i++) tr[i] = 0;}
	inline void upd(int x,int v) { for(int i = x;i <= n + n + 2;i += lowbit(i)) tr[i] += v;}
	inline int Sum(int x) { int res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
} T[2];
struct Event {
	int lim,id,op; 
	Event(){}
	Event(const int _lim,const int _id,const int _op):
		lim(_lim),id(_id),op(_op){}
};
vector<Event> Qs[N];
int Qi[N],Qr[N];
inline void Main() {
	scanf("%d%d",&n,&q);
	scanf("%s",s + 1);
	s[n + 1] = '#';
	for(int i = 1;i <= n;i++) ss[n + n + 2 - i] = ss[i] = s[i];
	Manacher();
	GetSa(ss,sa,n + n + 1,256);
	for(int i = 1;i <= n + n + 1;i++) rk[sa[i]] = i;
	// printf("rk: ");for(int i = 1;i <= n;i++) printf("%d ",rk[i]);printf("\n");
	// printf("rkR: ");for(int i = 1;i <= n;i++) printf("%d ",rk[Rev(i)]);printf("\n");
	// printf("R:");for(int i = 1;i <= n;i++) printf("%d ",R[i]);printf("\n");
	for(int i = 1;i <= n;i++) Qs[i].clear();
	for(int i = 1;i <= q;i++) 
		scanf("%d%d",&Qi[i],&Qr[i]),ans[i] = 0;
	for(int i = 1;i <= q;i++) {
		Qs[Qi[i]].emplace_back(rk[Qi[i]],i,1);
		Qs[Qi[i] + 2 * Qr[i]].emplace_back(rk[Qi[i]],i,-1);
	}
	T[0].Clr();T[1].Clr();
	for(int i = n;i >= 1;i--) {
		T[i & 1].upd(rk[Rev(i)],1);
		for(auto it : Qs[i]) 
			ans[it.id] += it.op * (T[(i-1)&1].Sum(n + n + 2) - T[(i-1)&1].Sum(it.lim));
	}	
	for(int i = 1;i <= n;i++) Qs[i].clear();
	T[0].Clr();
	for(int i = 1;i <= q;i++) {
		Qs[Qi[i] + 1].emplace_back(Qi[i],i,-1);
		Qs[Qi[i] + Qr[i] + 1].emplace_back(Qi[i],i,1);
	}
	for(int i = n;i >= 2;i--) {
		if(rk[i] < rk[Rev(i - 1)] && R[i])
			T[0].upd(i - R[i],1);
		for(auto it : Qs[i])
			ans[it.id] += it.op * (T[0].Sum(it.lim));
	}
	for(int i = 1;i <= q;i++)
		cout << ans[i] << endl;
}
int main() {
	int SubId,T;
	scanf("%d%d",&SubId,&T);
	while(T--) Main();
	return 0;
}
/*
0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3
*/