#include<bits/stdc++.h>
#define int long long
using namespace std;
int nxt[2000010],n;
string s;
int p,q;
int dp[1000010][30];
int dep[1000100];
int lg[1000010];
struct node{
	int to,nxt;
}a[2000010];
int head[10000100],tot;
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	dp[now][0]=fa;
	for(int i=1;i<=lg[dep[now]];i++){
		dp[now][i]=dp[dp[now][i-1]][i-1];
	}
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(fa==to)	continue;
		dfs(to,now);
	}
}
int lca(int x,int y){
	if(dep[x]<=dep[y]){
		swap(x,y);
	}
	while(dep[x]>dep[y]){
		x=dp[x][lg[dep[x]-dep[y]]];
	}
	if(x==y)	return nxt[x];
	for(int i=lg[dep[x]-1];i>=0;i--){
		if(dp[x][i]!=dp[y][i]){
			x=dp[x][i],y=dp[y][i];
		}
	}
	return dp[x][0];
}
int len;
void get_nxt(){
	int k=0;
	for(int i=2;i<=len;i++){
		while(k&&s[i]!=s[k+1])	k=nxt[k];
		if(s[i]==s[k+1])	k++;
		nxt[i]=k;add(k,i);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>s;
	cin>>n;
	s=" "+s;
	len=s.size()-1;
	get_nxt();
	lg[0]=-1;
	for(int i=1;i<=len;i++){
		lg[i]=lg[i>>1]+1;
	}
	lg[0]=0;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		cin>>p>>q;
		cout<<lca(p,q)<<'\n';
	}
	return 0;
}