#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
const int MAXN=5e5+10,INF=0x3f3f3f3f;
int n,qn; char S[MAXN];
vector<int> G[MAXN];
struct SAM{
    struct{ int fa,to[26],len,id; } T[MAXN];
    int nnd=1,prv=1,nid,rid[MAXN];
    void ins(int id,int c){
        int u=++nnd,v=prv; prv=u;
        T[u].len=T[v].len+1,T[u].id=id;
        for(; v&&!T[v].to[c]; v=T[v].fa) T[v].to[c]=u;
        if(!v){ T[u].fa=1; return; }
        int w=T[v].to[c];
        if(T[w].len==T[v].len+1){ T[u].fa=w; return; }
        int p=++nnd; T[p]=T[w],T[p].id=++nid,T[p].len=T[v].len+1;
        T[u].fa=T[w].fa=p;
        for(; v&&T[v].to[c]==w; v=T[v].fa) T[v].to[c]=p;
    }
    void build(){
        RNG(u,1,nnd) G[T[T[u].fa].id].push_back(T[u].id);
    }
} sam;
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN],top[MAXN];
void dfs1(int u,int fa_){
    fa[u]=fa_,dep[u]=dep[fa_]+1,siz[u]=1;
    for(int v:G[u]){
        if(v==fa_) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int top_){
    top[u]=top_;
    if(son[u]) dfs2(son[u],top_);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
int ans[MAXN];
struct Q1t{ int l,r,id; }; vector<Q1t> Q1[MAXN];
struct Q2t{ int l,r,id; }; vector<Q2t> Q2[MAXN];
struct SGT{
#define ls (u*2)
#define rs (u*2+1)
#define mid ((l+r)/2)
    static const int MAXN=2097152;
    int mn[MAXN],len;
    void pushup(int u){ mn[u]=min(mn[ls],mn[rs]); }
    void init(){
        for(len=1; len<n*2+2; len<<=1) ;
        IRNG(u,len*2-1,1) mn[u]=INF;
    }
    void upd(int i,int x){
        int u=i+len; mn[u]=x;
        for(u>>=1; u; u>>=1) pushup(u);
    }
    int qry(int u,int l,int r,int ql,int qr,int lim){
        if(ql<=l&&r<=qr){
            if(mn[u]>lim) return 0;
            if(l==r) return l;
            if(mn[ls]<=lim) return qry(ls,l,mid,ql,qr,lim);
            return qry(rs,mid+1,r,ql,qr,lim);
        }
        int ret=0;
        if(ql<=mid) ret=qry(ls,l,mid,ql,qr,lim);
        if(!ret&&mid<qr) ret=qry(rs,mid+1,r,ql,qr,lim);
        return ret;
    }
#undef ls
#undef rs
#undef mid
} sgt;
vector<int> vec;
void dfs6(int u,int r,int len){
    sgt.upd(u,u-len),vec.push_back(u);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[r]) dfs6(v,r,len);
    }
}
void dfs4(int u){
    dfs6(u,u,sam.T[sam.rid[u]].len);
    for(auto q:Q2[u]) ans[q.id]=max(ans[q.id],sgt.qry(1,0,sgt.len-1,q.l,q.r,q.l-1)-q.l+1);
    if(son[u]) dfs4(son[u]);
}
void dfs5(int u){
    if(son[u]) dfs5(son[u]);
    dfs6(u,u,0);
    for(auto q:Q1[u]) ans[q.id]=max(ans[q.id],sgt.qry(1,0,sgt.len-1,q.l,q.r,sam.T[sam.rid[u]].len+q.l-1)-q.l+1);
}
void dfs3(int u){
    for(int v:G[u]){
        if(v!=fa[u]) dfs3(v);
    }
    if(top[u]==u){
        auto clr=[](){
            for(int i:vec) sgt.upd(i,INF);
            vec.clear();
        };
        dfs4(u);
        clr();
        dfs5(u);
        clr();
    }
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>(S+1),n=int(strlen(S+1)),sam.nid=n+1,sam.T[1].id=n+1;
    RNG(i,1,n) sam.ins(i,S[i]-'a');
    sam.build();
    int rt=n+1;
    dfs1(rt,0),dfs2(rt,rt);
    cin>>qn;
    RNG(i,1,qn){
        int l,r; cin>>l>>r;
        for(int u=r; u; u=fa[top[u]]) Q1[u].push_back({l,r,i}),Q2[u].push_back({l,r,i});
    }
    sgt.init();
    dfs3(rt);
    RNG(i,1,qn) cout<<max(ans[i],0)<<"\n";
}