#include<bits/stdc++.h>
using namespace std;
char s[1100000];
int n,q,p[1100000];
int mst[21][1100000];
void init(){
	for(int i=1;i<=n;i++)mst[0][i]=p[i];
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			mst[j][i]=max(mst[j-1][i],mst[j-1][i+(1<<j-1)]);
}
int get(int l,int r){
	if(l>r)return -0x3f3f3f3f;
	int k=__lg(r-l+1);
	return max(mst[k][l],mst[k][r-(1<<k)+1]);
}
int main(){
	scanf("%s",s+1),n=strlen(s+1)*2+1,s[0]='&',s[n+1]='%';
	for(int i=n;i>=1;i--)s[i]=i%2?'$':s[i/2];
	for(int i=1,r,mid;i<=n;i++){
		if(i<=r)p[i]=min(r-i+1,p[r*2-i]);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]])p[i]++;
		if(i+p[i]-1>r)r=i+p[i]-1,mid=i;
	}
	init();
	scanf("%d",&q);
	for(int i=1,l,r;i<=q;i++){
		scanf("%d%d",&l,&r);
		int L=2,R=r-l+1,ans=1;l*=2,r*=2;
		while(L<=R){
			int mid=L+R>>1;
			if(get(l+mid-1,r-mid+1)>mid)ans=mid,L=mid+1;
			else R=mid-1;
		}
		printf("%d\n",ans);
	}
}