#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=5e5+5;
int typ,n,q;
char s[N];
int ans[N],c[N];
vector<tuple<int,int,int>>E;
int sa[N],rk[N],height[N],nxt[N];
vector<pair<int,int>>Q[N],nQ[N],A[N];
inline void add(int x,int y){
	for(;x<=n;x+=x&-x)c[x]+=y;
}
inline int sum(int x){
	int z=0;for(;x;x-=x&-x)z+=c[x];return z;
}
template<class T>inline void SA(T* s,int n){
	static int t1[N],t2[N],cnt[N];
	int *x=t1,*y=t2,m=128;
	for(int i=1;i<=n;++i)++cnt[x[i]=s[i]];
	for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;--i)sa[cnt[x[i]]--]=i;
	fill(cnt,cnt+m+1,0);
	for(int k=1;;k<<=1){
		int p=0;
		for(int i=n-k+1;i<=n;++i)y[++p]=i;
		for(int i=1;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;
		for(int i=1;i<=n;++i)++cnt[x[i]];
		for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;--i)sa[cnt[x[y[i]]]--]=y[i],y[i]=0;
		fill(cnt,cnt+m+1,0);
		swap(x,y),x[sa[p=1]]=1;
		for(int i=2;i<=n;++i)
			x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(sa[i]+k<=n?y[sa[i]+k]:0)==(sa[i-1]+k<=n?y[sa[i-1]+k]:0));
		if((m=p)>=n)break;
	}
	for(int i=1;i<=n;++i)rk[sa[i]]=i;
	for(int i=1,j=0;i<=n;++i){
		j=max(j-1,0);
		if(rk[i]==1)continue;
		int k=sa[rk[i]-1];
		while(i+j<=n&&j+k<=n&&s[i+j]==s[j+k])++j;
		height[rk[i]]=j;
	}
}
template<class T>inline void Z(T* s,int n){
	nxt[1]=n;
    for(int i=2,j=0,k=0;i<=n;++i){
        nxt[i]=max(min(k-i,nxt[i-j+1]),0);
        for(;i+nxt[i]<=n&&s[nxt[i]+1]==s[i+nxt[i]];++nxt[i]);
        if(i+nxt[i]>k)j=i,k=i+nxt[i];
    }
}
inline vector<int>Z(string s){
	const int n=s.length();
	s=" "+s,Z(s.c_str(),n);
	return vector<int>(nxt+1,nxt+n+1);
}
inline void solve(int l,int r){
	if(l==r)return;
	const int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	string u(s+l,s+mid+1),v(s+mid+1,s+r+1),ru(u.rbegin(),u.rend()),rv(v.rbegin(),v.rend());
	auto zx=Z(ru+'#'+rv),zy=Z(v+'#'+u);
	for(int i=0;i<r-l+1;++i){
		int p,k1,k2;
		if(i<mid-l+1)p=mid-l+1-i,k1=zx[p],k2=zy[r-mid+1+i];
		else p=i-(mid-l+1)+1,k1=zx[r-l+1-(p-1)],k2=zy[p];
		if(k1+k2>=p){
			if(i<mid-l+1){
				int x=max(1,p-k2),y=min(p,k1);
				if(y==p)--y;
				if(x<=y)E.emplace_back(l+i-y,l+i-x,p);
			}
			else{
				int x=max(1,p-k2),y=min(p,k1);
				if(x<=y)E.emplace_back(l+i-p+1-y,l+i-p+1-x,p);
			}
		}
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>typ;
	cin>>n>>q>>(s+1);
	SA(s,n);
	for(int i=1;i<=q;++i){
		int x,r;cin>>x>>r;
		Q[x].emplace_back(r,i);
		nQ[r].emplace_back(x,i);
	}
	for(int i=n;i>=1;--i){
		const int x=sa[i];
		for(auto [r,id]:Q[x])ans[id]+=sum(x+r)-sum(x);
		add(x,1);
	}
	solve(1,n);
	for(auto [x,y,l]:E)if(rk[y]<rk[y+l])A[l].emplace_back(x,y);
	fill_n(c+1,n,0);
	for(int i=1;i<=n;++i){
		for(auto [l,r]:A[i])add(l,1),add(r+1,-1);
		for(auto [x,id]:nQ[i])ans[id]-=sum(x);
	}
	for(int i=1;i<=q;++i)cout<<ans[i]<<'\n';
    return 0;
}
/*
*/