#include<bits/stdc++.h>
using namespace std;
struct time_helper{
#ifdef LOCAL
clock_t time_last;time_helper(){time_last=clock();}void test(){auto time_now=clock();std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;time_last=time_now;}~time_helper(){test();}
#else
void test(){}
#endif
}time_helper;
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
int print_precision=10;bool print_T_endl=1;char print_between=' ';
template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader;struct Writer;template<size_t id>struct read_tuple{template<typename...T>static void read(Reader&stream,std::tuple<T...>&x){read_tuple<id-1>::read(stream,x);stream>>get<id-1>(x);}};template<>struct read_tuple<0>{template<typename...T>static void read([[maybe_unused]]Reader&stream,[[maybe_unused]]std::tuple<T...>&x){}};template<size_t id>struct print_tuple{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){print_tuple<id-1>::print(stream,x);putchar(print_between);stream<<get<id-1>(x);}};template<>struct print_tuple<1>{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){stream<<get<0>(x);}};template<>struct print_tuple<0>{template<typename...T>static void print([[maybe_unused]]Writer&stream,[[maybe_unused]]const std::tuple<T...>&x){}};
struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename...T>Reader&operator>>(std::tuple<T...>&x){read_tuple<sizeof...(T)>::read(*this,x);return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}template<typename T1,typename T2>Reader&operator>>(std::pair<T1,T2>&x){*this>>x.first>>x.second;return *this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';
struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(const T&x){for(auto q:x){*this<<q;if(!is_class<decltype(q)>::value)*this<<print_between;}if(!is_class<typename T::value_type>::value&&print_T_endl)*this<<'\n';return *this;}template<typename...T>Writer&operator<<(const std::tuple<T...>&x){print_tuple<sizeof...(T)>::print(*this,x);if(print_T_endl)*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-print_precision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<print_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<print_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(const T&c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}template<typename T1,typename T2>Writer&operator<<(const std::pair<T1,T2>&x){*this<<x.first<<print_between<<x.second;if(print_T_endl)*this<<'\n';return *this;}Writer&operator<<(const std::string&str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<class Fun>class y_combinator_result{Fun fun_;public:template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}template<class ...Args>decltype(auto) operator()(Args &&...args){return fun_(std::ref(*this), std::forward<Args>(args)...);}};template<class Fun>decltype(auto) y_combinator(Fun &&fun){return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}

void init();void solve(int tc);
main()
{
	init();int t=1;
	// cin>>t;
	for(int tc=1;tc<=t;tc++)solve(tc);
}
void init()
{
}
struct sam
{
	string s;
	struct node
	{
		map<char,int>nxt;
		int pos,len,link,end;
	}st[1000001];
	int sa[1000001],tot=0;
	int cnt,lst;
	void dfs(int u)
	{
		if(st[u].end)sa[++tot]=st[u].pos;
		for(auto q:st[u].nxt)
		dfs(q.second);
	}
	void insert(int ch,int id)
	{
		int p=lst,cur=++cnt;
		// dbg(cur);
		st[cur].pos=id;
		st[cur].len=st[p].len+1;
		st[cur].end=1;
		while(p!=-1&&!st[p].nxt.count(ch))st[p].nxt[ch]=cur,p=st[p].link;
		if(p==-1)st[cur].link=0;
		else
		{
			int q=st[p].nxt[ch];
			if(st[q].len==st[p].len+1)
			{
				st[cur].link=q;
			}
			else
			{
				int clone=++cnt;
				st[clone]=st[q];
				st[clone].len=st[p].len+1;
				st[clone].end=0;
				while(p!=-1&&st[p].nxt.count(ch)&&st[p].nxt[ch]==q)st[p].nxt[ch]=clone,p=st[p].link;
				st[q].link=st[cur].link=clone;
			}
		}
		lst=cur;
	}
	int rk[1000001],stb[18][1000001],h[1000001];
	void buildsa(string s0)
	{
		st[0].link=-1;
		s=s0;
		int n=s.size();
		s=' '+s;
		for(int x=n;x>=1;x--)
		insert(s[x],x);
		for(int x=0;x<=cnt;x++)
		st[x].nxt.clear();
		for(int x=1;x<=cnt;x++)
		st[st[x].link].nxt[s[st[x].pos+st[st[x].link].len]]=x;
		dfs(0);
		for(int x=1;x<=n;x++)
		rk[sa[x]]=x;
		for(int x=1,y,z=0;x<=n;h[rk[x++]]=z)
		for(z=z?z-1:z,y=sa[rk[x]-1];s[x+z]==s[y+z];z++);
		for(int x=1;x<=n;x++)
		stb[0][x]=h[x];
		for(int x=1;1<<x<=n;x++)
		for(int y=1;y+(1<<x)-1<=n;y++)
		stb[x][y]=min(stb[x-1][y],stb[x-1][y+(1<<x-1)]);
	}
	int lcp(int a,int b)
	{
		if(a==b)return 1e9;
		a=rk[a],b=rk[b];
		if(a>b)swap(a,b);
		int k=__lg(b-a);
		return min(stb[k][a+1],stb[k][b-(1<<k)+1]);
	}
}a,b;
template<int ...ns>struct BIT;
template<int U,int ...ns>
struct BIT<U,ns...>
{
	BIT<ns...> BITT[U+10];
	void clear(){for(int x=0;x<U+10;x++)BITT[x].clear();}
	BIT(){clear();}
	template<typename T1,typename ...Tn>
	void add(const T1& n,const Tn& ...tn){for(int x=n+3;x<=U+5;x+=x&-x)BITT[x].add(tn...);}
	template<typename T1,typename ...Tn>
	int query(const T1& n,const Tn& ...tn){int r=0;for(int x=n+3;x;x-=x&-x)r+=BITT[x].query(tn...);return r;}
	template<typename T1,typename T2,typename ...Tn>
	int querylr(const T1& L,const T2& R,const Tn& ...tn){int r=0;for(int x=R+3;x;x-=x&-x)r+=BITT[x].querylr(tn...);for(int x=L+2;x;x-=x&-x)r-=BITT[x].querylr(tn...);return r;}
};
template<>
struct BIT<>
{
	int val;
	void clear(){val=0;}
	BIT(){clear();}
	void add(int u){val+=u;}
	int query(){return val;}
	int querylr(){return val;}
};
BIT<500001>bs;
void solve([[maybe_unused]]int tc)
{
	int n,q;
	cin>>n>>n>>q;
	string s;
	cin>>s;
	a.buildsa(s);
	reverse(s.begin(),s.end());
	b.buildsa(s);
	vector<vector<int>>g(n+1);
	for(int len=1;2*len<=n;len++)
	for(int x=len;x<=n;x+=len)
	{
		int l=x,r=x+len;
		int lcp=min(len,a.lcp(l,r));
		int lcs=min(len-1,b.lcp(n-l+2,n-r+2));
		if(lcp+lcs>=len)
		{
			int vlen=lcp+lcs-len+1;
			if(a.rk[l-lcs]<a.rk[l-lcs+len])g[l-lcs].emplace_back(len),g[l-lcs+vlen].emplace_back(-len);
		}
	}
	vector<vector<pair<int,int>>>qs(n+1);
	vector<int>res(q);
	for(int x=0;x<q;x++)
	{
		int pos,r;
		cin>>pos>>r;
		qs[pos].emplace_back(r,x);
	}
	for(int x=n;x>=1;x--)
	{
		for(auto [r,id]:qs[a.sa[x]])
		{
			res[id]+=bs.querylr(a.sa[x],a.sa[x]+r);
		}
		bs.add(a.sa[x],1);
	}
	bs.clear();
	for(int x=1;x<=n;x++)
	{
		for(auto q:g[x])
		if(q>0)bs.add(q,1);
		else bs.add(-q,-1);
		for(auto [r,id]:qs[x])
		{
			res[id]-=bs.query(r);
		}
	}
	print_between='\n';
	print_T_endl=0;
	cout<<res;
}