#include<bits/stdc++.h>
#define maxh 20
#define maxn 1000050
using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y) {
    if (!b)
        return x=1,y=0,a;
    else {
        LL g=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return g;
    }
}

struct ArithmeticSeq {
    int a0,d,n;
    ArithmeticSeq(set<int> s)   {
        if (!s.size())
            a0=d=n=0;
        else {
            a0=*s.rbegin();
            d=(*s.rbegin()-*s.begin())/s.size();
            n=s.size();
            for (int i=0;i<n;++i)
                assert(s.count(a0+i*d));
        }
        normalize();
    }

    ArithmeticSeq(int _a0=0,int _d=1,int _n=0):a0(_a0),d(_d),n(_n)  {
        normalize();
    }

    ArithmeticSeq cut(int lim) {
        // a0+kd>=lim
        if (a0>=lim) return *this;
        int k=(lim-a0+d-1)/d;
        if (k>=n) return ArithmeticSeq();
        return ArithmeticSeq(a0+k*d,d,n-k);
    }

    void normalize()    {
        if (n<=1) d=1;
        assert(d>0);
    }
    int last()  {
        return a0+(n-1)*d;
    }
    vector<int> getSeq()    {
        vector<int> v;
        for (int i=0;i<n;++i)
            v.push_back(a0+i*d);
        return v;
    }
    // bool contains(int x)    {
    //     if ((x-a0)%d) return 0;
    //     int k=(x-a0)/d;
    //     return 0<=k&&k<n;
    // }
    friend ArithmeticSeq operator - (int x,ArithmeticSeq aq)   {
        return ArithmeticSeq(x-(aq.a0+(aq.n-1)*aq.d),aq.d,aq.n);
    }
    friend ArithmeticSeq operator + (int x,ArithmeticSeq aq)   {
        return ArithmeticSeq(x+aq.a0,aq.d,aq.n);
    }
    friend ArithmeticSeq operator & (ArithmeticSeq a,ArithmeticSeq b)    {
        if (a.a0>b.a0) swap(a,b);
        if (a.last()<b.a0) return ArithmeticSeq();
        // cout<<a<<" "<<b<<endl;
        assert(a.d>0&&b.d>0);
        LL x,y;
        // x*a.d+y.b.d = b.a0-a.a0
        LL g=exgcd(a.d,b.d,x,y),lcm=(LL)a.d*b.d/g;
        if ((b.a0-a.a0)%g) return ArithmeticSeq();

        // cout<<a.d*x+b.d*y<<" "<<b.a0-a.a0<<endl;

        x*=(b.a0-a.a0)/g;
        y*=-(b.a0-a.a0)/g;
        // cout<<a.a0+x*a.d<<" "<<b.a0+y*b.d<<endl;
        assert(a.a0+x*a.d==b.a0+y*b.d);

        LL same=a.a0+x*a.d;
        // same+k*lcm>=a0
        LL a_nxt=same+((a.a0-same+lcm-1)/lcm)*lcm;
        LL b_nxt=same+((b.a0-same+lcm-1)/lcm)*lcm;

        // cout<<same<<" "<<a.a0<<" "<<b.a0<<endl;

        LL new_a0=max(a_nxt,b_nxt);
        if (new_a0>a.last()||new_a0>b.last())
            return ArithmeticSeq();
        else {
            int new_n=min((a.last()-new_a0)/lcm,(b.last()-new_a0)/lcm)+1;
            return ArithmeticSeq(new_a0,lcm,new_n);
        }
        // cout<<a<<" "<<b<<endl;
        // if (a.d==b.d)   {
        //     int st=max(a.a0,b.a0),ed=min(a.a0+(a.n-1)*a.d,b.a0+(b.n-1)*b.d);
        //     return ArithmeticSeq(st,a.d,(ed-st)/a.d+1);
        // } else {
        //     if (a.n>b.n) swap(a,b);
        //     assert(a.n<=2);
        //     vector<int> sa=a.getSeq();
        //     set<int> res;
        //     for (int x:sa)  
        //         if (b.contains(x))
        //             res.insert(x);
        //     return ArithmeticSeq(res);
        // }
    }
    friend ostream& operator << (ostream& os,ArithmeticSeq aq)   {
        os<<"("<<aq.a0<<","<<aq.d<<","<<aq.n<<")";
        return os;
    }
};


int n,q;
char s[maxn];
int qLen[maxn];
int L[maxn],R[maxn];

int longest[maxn];

LL ans[maxn];

struct SA {

    int sa[maxn],rk[maxn];

    int Log2[maxn];
    int ST[maxh][maxn],* const h=ST[0];

    int sat[maxh][maxn],rkt[maxh][maxn];
    int st[maxh][maxn],ed[maxh][maxn];

    LL cnt[maxn];

    // template<LL base,LL modu>
    // struct HASH {
    //     LL h[maxn],pw[maxn];
    //     HASH()  {
    //         for (int i=pw[0]=1;i<maxn;++i)
    //             pw[i]=pw[i-1]*base%modu;
    //     }
    //     void build(char *s,int n)   {
    //         for (int i=1;i<=n;++i) 
    //             h[i]=(h[i-1]*base+s[i]-'a'+1)%modu;
    //     }
    //     LL operator ()(int l,int r) {
    //         return (h[r]+(modu-h[l-1])*pw[r-l+1])%modu;
    //     }
    // };

    // HASH<31,998244353> H1;
    // HASH<131,1000000007> H2;

    // pair<LL,LL> gethash(int l,int r)    {
    //     return make_pair(H1(l,r),H2(l,r));
    // }

    void build(char *s,int n)    { // no zero
        static int ts[2][maxn],sum[maxn];

        int *x=ts[0],*y=ts[1],m=256; // attention
        for (int i=1;i<=m;++i) sum[i]=0;
        for (int i=1;i<=n;++i) ++sum[x[i]=s[i]];
        for (int i=1;i<=m;++i) sum[i]+=sum[i-1];
        for (int i=n;i;--i) sa[sum[s[i]]--]=i;
        
        for (int b=0;(1<<b)<=n;++b)    {                
            auto calcnxt=[&]()  {
                memcpy(rkt[b],x,sizeof(rkt[b]));
                memcpy(sat[b],sa,sizeof(sat[b]));
                // cout<<"sat["<<b<<"]="; for (int i=1;i<=n;++i) cout<<sa[i]<<" "; cout<<endl;
                for (int i=n,j=n;i;i=j)  {
                    for (;j&&x[sa[i]]==x[sa[j]];--j)
                        ed[b][sa[j]]=i;
                    for (;i>j;--i)
                        st[b][sa[i]]=j+1;
                }
            };
            calcnxt();

            // cout<<"--------------------"<<endl;

            int p=0,k=1<<b;
            for (int i=n;i>n-k;--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<=m;++i) sum[i]=0;
            for (int i=1;i<=n;++i) ++sum[x[y[i]]];
            for (int i=1;i<=m;++i) sum[i]+=sum[i-1];
            for (int i=n;i;--i) sa[sum[x[y[i]]]--]=y[i];
            swap(x,y);
            m=x[sa[1]]=1;
            for (int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?m:++m);
        }

        for (int i=1;i<=n;++i) rk[sa[i]]=i;
        for (int i=1,k=0;i<=n;++i)  {
            if (k) --k;
            int j=sa[rk[i]-1];
            while (s[i+k]==s[j+k]) ++k;
            h[rk[i]]=k;
        }

        for (int i=1;i<=n;++i) cnt[i]=cnt[i-1]+n-sa[i]+1-h[i];

        // for (int i=1;i<=n;++i) cout<<"cnt["<<i<<"]="<<cnt[i]<<endl;

        Log2[0]=-1;
        for (int i=1;i<=n;++i) Log2[i]=Log2[i>>1]+1;
        for (int j=1;j<=Log2[n];++j)
            for (int i=1;i+(1<<j)-1<=n;++i)
                ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<j-1)]);
    }
    inline int lcp(int i,int j)    {
        if (i>n||j>n) return 0;
        if (i==j) return maxn;
        int l=rk[i],r=rk[j];
        if (l>r) swap(l,r);
        ++l;
        int t=Log2[r-l+1];
        return min(ST[t][l],ST[t][r-(1<<t)+1]);
    }

    inline int compare(int i,int j)    {
        // return s[i:]<s[j:]
        if (i>n&&j>n) return 0;
        if (i>n||j>n) return i>n;
        return rk[i]<rk[j];
    }

    LL calcSmallerSuffix(int a,int b,char c) {
        // cerr<<"???:"<<rk[l]<<" "<<cnt[rk[l]-1]<<" "<<max(0,r-l+1-h[rk[l]])<<" "<<(r-l+1)<<endl;
        int len=b-a+1,lim=getLeftmostEqual(a,b);
        int l=lim-1,r=getRightmostEqual(a,b);
        // cerr<<"???:"<<a<<" "<<b<<" "<<c<<endl;
        while (l<r) {
            int mid=(l+r+1)>>1;
            // cerr<<l<<" "<<r<<":"<<mid<<" "<<sa[mid]<<" "<<len<<" "<<n<<" |"<<s[sa[mid]+len]<<"|"<<endl;
            assert(sa[mid]<=n-len+1);
            if (s[sa[mid]+len]<c)
                l=mid;
            else
                r=mid-1;
        }
        // cout<<l<<" "<<r<<endl;
        return cnt[l]-min(lcp(sa[l],a),len);
    }

    int getMaxRepeatedPrefix(int l,int r,int p) {
        int len=r-l+1;
        if (lcp(l,p)<len) return 0;
        return lcp(p,p+len)/len+1;
    }

    int getMaxRepeatedPrefixLen(int l,int r,int p) {
        int len=r-l+1,t=lcp(l,p);
        if (t<len) return t;
        return lcp(p,p+len)+len;
    }

    int getSmallerCnt(ArithmeticSeq stpos,int i) {
        // return \sum_{p\in stpos} s[p:]<s[i:]
        assert(stpos.d>0);
        int offset=getMaxRepeatedPrefix(stpos.a0,stpos.a0+stpos.d-1,stpos.last());
        int times=getMaxRepeatedPrefix(stpos.a0,stpos.a0+stpos.d-1,i);
        // cout<<"???:"<<stpos<<" "<<i<<" "<<times<<endl;

        auto calc=[&](ArithmeticSeq stpos)  {
            int cnt=0;
            if (stpos.n<=1) {
                vector<int> v_stpos=stpos.getSeq();
                for (int p:v_stpos)
                    cnt+=compare(p,i);
            } else {
                //[0,times) : stpos.last(), stpos.a0
                if (compare(stpos.last(),stpos.a0))
                    cnt+=min(times,stpos.n);
                
                // times
                if (stpos.n>times)
                    cnt+=compare(stpos.last(),i+times*stpos.d);
                
                // (times,n)
                if (stpos.n>times+1&&compare(stpos.a0,i+times*stpos.d))
                    cnt+=stpos.n-times-1;
            }
            // cout<<"calc:"<<stpos<<" "<<i<<" ~ "<<cnt<<endl;
            return cnt;
        };

        int res=calc(ArithmeticSeq(stpos.a0,stpos.d,stpos.n+offset))-calc(ArithmeticSeq(stpos.last()+stpos.d,stpos.d,offset));
        return res;
    }

    ArithmeticSeq getEqual(int p,int k,int l,int r)    {
        //s[p,p+2^k) 
        //return all start pos in [l,r]
        int a=lower_bound(sat[k]+st[k][p],sat[k]+ed[k][p]+1,l)-sat[k];
        int b=upper_bound(sat[k]+st[k][p],sat[k]+ed[k][p]+1,r-(1<<k)+1)-sat[k]-1;
        // cout<<"get("<<p<<","<<k<<","<<l<<","<<r<<") "; for (int i=st[k][p];i<=ed[k][p];++i) cout<<sat[k][i]<<" "; cout<<endl;
        // cout<<"a,b="<<a<<","<<b<<endl;
        assert(b-a+1<=1||sat[k][b]-sat[k][b-1]==sat[k][a+1]-sat[k][a]);
        return ArithmeticSeq(sat[k][a],sat[k][a+1]-sat[k][a],b-a+1);
    }

    int getLeftmostEqual(int a,int b)   {
        int l=1,r=rk[a];
        while (l<r)    {
            int mid=(l+r)>>1;
            if (lcp(sa[mid],a)>=b-a+1)
                r=mid;
            else
                l=mid+1;
        }
        return l;
        
        int lim=b-a+1,p=rk[a];
        // cerr<<(1<<Log2[n-p+1])<<endl;
        for (int i=Log2[p];i>=0;--i)
            if (p-(1<<i)>0&&ST[i][p-(1<<i)+1]>=lim)
                p-=(1<<i);
        return p;
    }    
    
    int getRightmostEqual(int a,int b)   {
        int l=rk[a],r=n;
        while (l<r)    {
            int mid=(l+r+1)>>1;
            if (lcp(sa[mid],a)>=b-a+1)
                l=mid;
            else
                r=mid-1;
        }
        return l;

        
        int lim=b-a+1,p=rk[a];
        // cerr<<(1<<Log2[n-p+1])<<endl;
        for (int i=Log2[n-p+1];i>=0;--i)
            if (p+(1<<i)<=n&&ST[i][p+1]>=lim)
                p+=(1<<i);
        return p;
    }
    inline pair<int,int> getRange(int a,int b) {
        return make_pair(
            getLeftmostEqual(a,b),
            getRightmostEqual(a,b));
    }
    // inline void getRange(int a,int b,int &l,int &r) {
    //     l=getLeftmostEqual(a,b);
    //     r=getRightmostEqual(a,b);
    // }
} S,T;

namespace BIT  {
    int T[maxn];
    inline int lowbit(int x)    {
        return x&-x;
    }
    void add(int i) {
        for (;i<=n;i+=lowbit(i))
            ++T[i];
    }
    int query(int i)    {
        int ans=0;
        for (;i;i-=lowbit(i))
            ans+=T[i];
        return ans;
    }
}

int CNT=0;

void getRepeat()    {
    for (int i=1;i<=q;++i)  {
        int l=1,r=n+1;
        while (l<r) {
            int mid=(l+r)>>1;
            auto check=[&](int p)->bool    {
                int len=S.getMaxRepeatedPrefixLen(L[i],R[i],p);
                assert(len<=n-p+1);
                if (len==n-p+1) return 0;
                return s[p+len]>s[L[i]+len%qLen[i]];
            };
            if (check(S.sa[mid]))
                r=mid;
            else
                l=mid+1;
        }
            // cout<<i<<":"<<L[i]<<" "<<R[i]<<endl;
        //sa[l-1]^inf<=substr^inf<=sa[l]^inf
        if (l>1)    {
            // cout<<"l-1:"<<string(s+S.sa[l-1],s+n+1)<<endl;
            int t=S.getMaxRepeatedPrefixLen(L[i],R[i],S.sa[l-1]);
            if (t>longest[i])   {
                L[i]=S.sa[l-1];
                R[i]=L[i]+qLen[i]-1;
                longest[i]=t;
            }
        }
        if (l<=n)   {
            // cout<<"l:"<<string(s+S.sa[l],s+n+1)<<endl;
            int t=S.getMaxRepeatedPrefixLen(L[i],R[i],S.sa[l]);
            if (t>longest[i])   {
                L[i]=S.sa[l];
                R[i]=L[i]+qLen[i]-1;
                longest[i]=t;
            }
        }
        R[i]=L[i]+longest[i]-1;
            // cout<<i<<":"<<L[i]<<" "<<R[i]<<" "<<endl;
    }
    for (int i=1;i<=q;++i)  {
        char nxt=s[L[i]+(R[i]-L[i]+1)%qLen[i]];
        // cout<<i<<":"<<longest[i]<<endl;
        // cerr<<i<<":"<<S.calcSmallerSuffix(L[i],R[i],nxt)<<" "<<nxt<<endl;
        ans[i]+=S.calcSmallerSuffix(L[i],R[i],nxt);
    }
}


int calcCyclicShift(int l,int r,int repeatedLen) {
    // cout<<"calcCyclicShift:"<<l<<" "<<r<<" "<<repeatedLen<<endl;
    int originalLen=(r-l+1);
    int repeatedTimes=repeatedLen/originalLen,scatteredLen=repeatedLen%originalLen;
    vector<ArithmeticSeq> borders;
    for (int b=0;(1<<b)<originalLen;++b)  {
        // cout<<"b:"<<b<<endl;
        int stLen=1<<b,edLen=min((1<<b+1),originalLen)-1;
        //only consider border len in [st,ed]
        // cout<<"["<<stLen<<","<<edLen<<"]"<<endl;
        auto front=S.getEqual(l,b,r-edLen+1,r),back=S.getEqual(r-stLen+1,b,l,l+edLen-1);
        if (!front.n||!back.n) continue;
        // cout<<front<<" "<<back<<endl;
        auto border=(r+1-front)&(stLen-l+back);
        borders.push_back(border);
    }
    int res=0;
    // cout<<"initial:"<<res<<endl;
    auto calc=[&](ArithmeticSeq border) {
        if (!border.n) return 0;
        int res=0;
        // cout<<border<<endl;
        // s[l,r]=s[l,r-border]+s(r-border,border]=a+b(order), judge a: aab<aba -> ab<ba?

        // minus s[l+|b|:]<s[r+1:]
        // cout<<"minus:"<<S.getSmallerCnt(l+border,r+1)<<endl;
        res-=S.getSmallerCnt(l+border,r+1);

        // judge s[l+|b|,r]<a
        // plus s[l+|b|:]<s[l:]
        // cout<<"plus:"<<S.getSmallerCnt(l+border,l)<<endl;
        res+=S.getSmallerCnt(l+border,l);
        // minus s(r:]<s[l+|a|:] if s[l,r-|b|] == s[l+|b|,r]
        for (auto tmp_border:borders)   {
            ++CNT;
            auto complement_border=tmp_border&(originalLen-border);

            // cout<<tmp_border<<" & "<<originalLen-border<<" = "<<complement_border<<endl;
            if (!complement_border.n) continue;
            // cout<<"minus:"<<complement_border<<" "<<complement_border.n<<"-"<<S.getSmallerCnt(complement_border,r+1)<<endl;
            res-=complement_border.n-S.getSmallerCnt(l+complement_border,r+1);
        }
        // cout<<"res:"<<res<<endl;
        return res;
    };

    for (auto border:borders)  {
        // cout<<"border:"<<border<<endl;
        res+=repeatedTimes*calc(border);
        auto rest=border.cut(originalLen-scatteredLen);
        res+=calc(rest);
    }
    return res;
}

vector<int> Q[maxn];

int main()  {
    // cout<<(ArithmeticSeq(3,1,1)&ArithmeticSeq(2,2,2))<<endl;
    // return 0;
    scanf("%s%d%*d",s+1,&q),n=strlen(s+1);
    S.build(s,n);
    // cout<<"S:"<<endl; for (int i=1;i<=n;++i) cout<<S.sa[i]<<":"<<string(s+S.sa[i],s+n+1)<<endl;

    for (int i=1;i<=q;++i)
        scanf("%d%d",L+i,R+i),qLen[i]=longest[i]=R[i]-L[i]+1;
    
    cerr<<"input:"<<clock()<<endl;
    getRepeat();

    cerr<<"getRepeat:"<<clock()<<endl;
    for (int i=1;i<=q;++i)  
        Q[S.rk[L[i]]].push_back(i);
    for (int i=n;i;--i) {
        BIT::add(S.sa[i]);
        for (int j:Q[i])    {
            int l=L[j],r=L[j]+qLen[j]-1;
            int originalLen=qLen[j];
            int repeatedLen=longest[j],scatteredLen=repeatedLen%originalLen;
            int suml=BIT::query(l),sumr=BIT::query(r),sums=BIT::query(l+scatteredLen);
            ans[j]+=(sumr-suml)*(repeatedLen/originalLen)+
                    (sums-suml);
        }
    }
    for (int i=1;i<=q;++i)
        ans[i]+=calcCyclicShift(L[i],L[i]+qLen[i]-1,R[i]-L[i]+1);

    for (int i=1;i<=q;++i)
        printf("%lld\n",ans[i]);

    cerr<<"std2 inspired by claris:"<<clock()<<" "<<CNT<<endl;
    return 0;
}