#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
string s;
int p,q,m,nxt[maxn],fa[maxn][22],lg[maxn],depth[maxn];
vector<int> g[maxn];
void dfs(int u,int fath)
{
	fa[u][0]=fath;
	for(int i=1;i<=lg[depth[u]];i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int v : g[u])
	{
		depth[v]=depth[u]+1;
		dfs(v,u);
	}
}
int get(int a,int b){
	if(depth[a]<depth[b]) swap(a,b);
	while(depth[a]>depth[b]) a=fa[a][lg[depth[a]-depth[b]]];
	if(a==b) return a;
	for(int i=lg[depth[a]];i>=0;i--)
	{
		if(fa[a][i]!=fa[b][i])
		{
			a=fa[a][i];b=fa[b][i];
		}
	}
	return fa[a][0];
}
int main()
{
	cin>>s;
	
	nxt[0]=0;
	int j=0;
	for(int i=1;i<s.size();i++)
	{
		while(j&&s[j+1]!=s[i]) j=nxt[j];
		if(s[j+1]==s[i]) j++;
		nxt[i]=j;
	}
	for(int i=0;i<s.size();i++)
	{
		g[nxt[i]].push_back(i);
	}
	lg[1]=0;
	for(int i=2;i<=s.size();i++)
	{
		lg[i]=lg[i-1]+((i&-i)==i);
	}
	depth[0]=0;dfs(0,0);
	cin>>m;
	while(m--)
	{
		scanf("%d%d",&p,&q);
		printf("%d\n",get(fa[p][0],fa[q][0]));
	}
	return 0;
}