#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
//#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!isalnum(ch)) ch=getchar();
		while(isalnum(ch)){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!isalnum(ch)) ch=getchar();
		return ch;
	}
	inline void putstr(string s){
		int len=s.length();
		for(int i=0;i<len;++i) putchar(s[i]);
	}
}
using namespace quickread;
const int N=1e6+10,inf=2147483647;
int n,m,dp[N][30],dep[N],lg[N],fail[N];
string s;
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] ] - 1 ];
	if(!(x^y)) return x;
	for(int i=lg[dep[x]]-1;~i;--i) 	if(dp[x][i]^dp[y][i]) x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//	freopen("P5829.in","r",stdin);
//	freopen("P5829.out","w",stdout);
	s=readstr();n=s.length();s=' '+s;
	for(int i=2,j=0;i<=n;++i){
		while(j&&s[i]^s[j+1]) j=fail[j];
		if(s[i]==s[j+1]) ++j;
		fail[i]=j;dep[i]=dep[j]+1,dp[i][0]=j; 
	}
	for(int i=1;i<=21;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int k=1;k<=21;++k) for(int i=1;i<=n;++i) dp[i][k]=dp[dp[i][k-1]][k-1];
//	for(int i=1;i<=n;++i){
//		write(i),putchar(':');
//		for(int j=0;j<=21;++j)
//			write(dp[i][j]),kg;
//		hh;
//	}
	read(m);
	while(m--){
		int x,y;read(x),read(y);
		int z=lca(x,y);
//		write(z),kg;
		if(!z) puts("0");
		else if(z==x||z==y) write(fail[z]),hh;
		else write(z),hh; 
 	}
	return 0;
}

链接