#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 500500
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

int n,q;
char s[N],t[N];

struct Suffix_Array
{
    int sa[N],rk[N],x[N],y[N],buc[N],m,tot,st[20][N],*h=st[0];

    IL int min(reg int x,reg int y){return x<y?x:y;}

    IL int lcp(reg int x,reg int y)
    {
        if(x==y)return n-x+1;
        x=rk[x],y=rk[y];
        if(x>y)std::swap(x,y);
        ++x;
        reg int o=std::__lg(y-x+1);
        return min(st[o][x],st[o][y-(1<<o)+1]);
    }

    IL void init(char *s)
    {
        m='z';
        for(reg int i=1;i<=n;++i)++buc[x[i]=s[i]];
        for(reg int i=1;i<=m;++i)buc[i]+=buc[i-1];
        for(reg int i=n;i;--i)sa[buc[x[i]]--]=i;
        for(reg int k=1,i;;k<<=1)
        {
            tot=0;
            for(i=n;i>n-k;--i)y[++tot]=i;
            for(i=1;i<=n;++i)if(sa[i]>k)y[++tot]=sa[i]-k;
            for(i=1;i<=m;++i)buc[i]=0;
            for(i=1;i<=n;++i)++buc[x[i]];
            for(i=1;i<=m;++i)buc[i]+=buc[i-1];
            for(i=n;i;--i)sa[buc[x[y[i]]]--]=y[i];
            for(i=1;i<=n;++i)y[i]=x[i];
            x[sa[1]]=1;
            for(i=2;i<=n;++i)x[sa[i]]=x[sa[i-1]]+(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]);
            if((m=x[sa[n]])==n)break;
        }
        for(reg int i=1;i<=n;++i)rk[i]=x[i];
        for(reg int i=1,j,k=0;i<=n;++i)if(rk[i]>1)
        {
            if(k)--k; j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])++k;
            h[rk[i]]=k;
        }
        for(reg int o=1,i;o<20;++o)for(i=1;i+(1<<o)-1<=n;++i)
            st[o][i]=min(st[o-1][i],st[o-1][i+(1<<o-1)]);
    }
}A,B;

IL void cmin(reg int &x,reg int y){x>y?x=y:0;}
IL void cmax(reg int &x,reg int y){x<y?x=y:0;}

int ans[N];
std::vector<std::pair<int,int>>vec1[N],vec2[N],shelf[N];
int c[N];

IL int low(reg int x){return x&-x;}
IL int ask(reg int x){reg int r=0; for(;x;x-=low(x))r+=c[x]; return r;}
IL void add(reg int x,reg int k){for(;x<=n;x+=low(x))c[x]+=k;}
IL void clear(){std::fill(c+1,c+1+n,0);}

main()
{
    read(),n=read(),q=read();
    scanf("%s",s+1);
    for(reg int i=1;i<=n;++i)t[n-i+1]=s[i];
    A.init(s),B.init(t);
    for(reg int k=1,i,j,l,r,p;k<=n;++k)for(i=k,j=k+k;j<=n;i+=k,j+=k)
    {
        l=i+1,r=j;
        p=B.lcp(n-i+1,n-j+1),cmax(l,j-p+1);
        p=A.lcp(i,j),cmin(r,j+p-k);
        if(l<=r&&A.rk[r-k]<A.rk[r])
            shelf[l-k].push_back({k,1}),shelf[r-k+1].push_back({k,-1});
    }
    for(reg int i=1,x,k;i<=q;++i)
    {
        x=read(),k=read();
        vec1[x].push_back({k,i});
        vec2[x].push_back({k,i});
    }
    for(reg int i=1;i<=n;++i)
    {
        for(auto &[x,k]:shelf[i])add(x,k);
        for(auto &[x,id]:vec1[i])ans[id]=-ask(x);
    }
    clear();
    for(reg int i=n,x;i;--i)
    {
        add(x=A.sa[i],1);
        for(auto &[k,id]:vec2[x])
            ans[id]+=ask(x+k)-ask(x);
    }
    for(reg int i=1;i<=q;++i)printf("%d\n",ans[i]);
}