#include<bits/stdc++.h>
using namespace std;
int n,T,w[1000005],st[2000005][25],lg[2000005];
char s[1000005];
int change(int n){
	static char tmp[1000005];
	int m=0;tmp[++m]='$';
	for(int i=1;i<=n;i++)tmp[++m]=s[i],tmp[++m]='$';
	for(int i=1;i<=m;i++)s[i]=tmp[i];
	return m;
}
void manacher(int n){
	for(int i=2,p=1;i<=n;i++){
		if(i<=p+w[p])w[i]=min(p+w[p]-i,w[2*p-i]);
		while(i+w[i]+1<=n&&i-w[i]-1>=1&&s[i+w[i]+1]==s[i-w[i]-1])w[i]++;
		if(p+w[p]<i+w[i])p=i;
	}
}
void init(){
	memset(st,128,sizeof(st));
	for(int i=1;i<=n;i++)st[i][0]=w[i];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r){
	if(l>r)return 0;
	int t=lg[r-l+1];
	return max(st[l][t],st[r-(1<<t)+1][t]);
}
signed main(){
	scanf("%s",s+1);n=strlen(s+1);
	n=change(n);manacher(n);
	scanf("%d",&T);
	init();
	while(T--){
		int l,r;scanf("%d%d",&l,&r);
		l=l*2-1,r=r*2+1;
		int ans=1,ll=1,rr=r-l+1,mid=0;
		while(ll<=rr){
			mid=(ll+rr)>>1;
			if(query(l+mid,r-mid)>=mid)ans=mid,ll=mid+1;
			else rr=mid-1;
		}
		printf("%d\n",ans);
	}
}