#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
string s;
int n,m,p,q;
int nxt[2000100];
int fa[22][2000100];
int dep[2000100];
signed main(){
	cin >> s;
	n=s.size();
	s=' '+s;
	fa[0][0]=fa[0][1]=n+1;
	dep[n+1]=0;
	dep[1]=1;
	dep[0]=1;
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[j+1]!=s[i])j=nxt[i];
		if(s[j+1]==s[i])++j;
		nxt[i]=j;
		fa[0][i]=j;
		dep[i]=dep[j]+1;
	}
	for(int j=1;j<=21;j++){
		for(int i=0;i<=n;i++){
			fa[j][i]=fa[j-1][fa[j-1][i]];
		}
	}
	R(m);
	while(m--){
		R(p);R(q);
		if(dep[p]<dep[q])swap(p,q);
		for(int i=21;i>=0;i--)if(dep[fa[i][p]]>=dep[q])p=fa[i][p];
		for(int i=21;i>=0;i--)if(fa[i][p]^fa[i][q])p=fa[i][p],q=fa[i][q];
		write(fa[0][p]==n+1?0:fa[0][p]);push('\n');
	}
    return 0;
}