#include<bits/stdc++.h>
using namespace std;

struct BorderTree{
    int fa[20],dis;
    char data;
};

BorderTree t[1000001];
int n,logn;

void build(string s){
    n=s.length();
    logn=log2(n)+1;
    for(int i=1;i<=n;i++)
    t[i].data=s[i-1];
    t[0].fa[0]=0;t[0].dis=0;
    t[1].fa[0]=0;t[1].dis=1;
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&t[i].data!=t[j+1].data) j=t[j].fa[0];
        if(t[i].data==t[j+1].data) j++;
        t[i].dis=t[j].dis+1;
        t[i].fa[0]=j;
    }
    for(int x=0;x<=n;x++)
    for(int i=1;i<=logn;i++)
    t[x].fa[i]=t[t[x].fa[i-1]].fa[i-1];
}

int lca(int x,int y){
    if(t[x].dis<t[y].dis) return lca(y,x);

    for(int i=logn;i>=0;i--)
    if(t[t[x].fa[i]].dis>=t[y].dis)
    x=t[x].fa[i];

    if(x==y) return t[x].fa[0];

    for(int i=logn;i>=0;i--)
    if(t[x].fa[i]!=t[y].fa[i]){
        x=t[x].fa[i];
        y=t[y].fa[i];
    }

    return t[x].fa[0];
}

int main(){
    string s;
    cin>>s;
    build(s);
    int m,p,q;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>p>>q;
        cout<<lca(p,q)<<endl;
    }
    return 0;
}