#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() {
	cin >> n >> q;
	cin >> (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++) 
		cin >> 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;
	cin >> 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
*/

answer.code: In function ‘void Main()’:
answer.code:61:13: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘char*’)
   61 |         cin >> (s + 1);
      |         ~~~ ^~ ~~~~~~~
      |         |         |
      |         |         char*
      |         std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:168:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:168:7: note:   conversion of argument 1 would be ill-formed:
answer.code:61:19: error: cannot bind non-const lvalue reference of type ‘bool&’ to a value of type ‘char*’
   61 |         cin >> (s + 1);
      |                ~~~^~~~
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:172:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:172:7: note:   conversion of argument 1 would be ill-formed:
answer.code:61:19: error: invalid conversion from ‘char*’ to ‘short int’ [-fpermissive]
   61 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:61:19: error: cannot bind rvalue ‘(short int)(((char*)(& s)) + 1)’ to ‘short int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:175:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:175:7: note:   conversion of argument 1 would be ill-formed:
answer.code:61:19: error: invalid conversion from ‘char*’ to ‘short unsigned int’ [-fpermissive]
   61 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:61:19: error: cannot bind rvalue ‘(short unsigned int)(((char*)(& s)) + 1)’ to ‘short unsigned int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:179:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:179:7: note:   conversion of argument 1 would be ill-formed:
answer.code:61:19: error: invalid conversion from ‘char*’ to ‘int’ [-fpermissive]
   61 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:61:19: error: cannot bind rvalue ‘(int)(((char*)(& s)) + 1)’ to ‘int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:182:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:182:7: note:   conversion of argument 1 would be ill-formed:
answer.code:61:19:...