#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define int long long
#define db long double
#define pii pair<int,int>
#define st first
#define ed second
#define mkp make_pair
#define pb push_back
#define eps 1e-9
#define mod 998244353
#define mod2 1000000007
#define bs 13131
#define bs2 131
#define INF 0x3f3f3f3f3f3f3f3f
#define il inline
#define vi vector<int>
#define ins insert
#define umap unordered_map
#define uset unordered_set
#define R(x) x.begin(),x.end()
#define B(x) x.begin()
#define E(x) x.end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
il int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int T=1,n,m,q,k;
char c[N];
il void solve(){
	n=read();
}
int f[21][N];
int lg[N];
il int query(int l,int r){
	if(l>r)return -INF;
	int k=lg[r-l+1];
	return max(f[k][l],f[k][r-(1<<k)+1]);
}
signed main(){
	scanf("%s",c+1);
	n=strlen(c+1);
	for(int i=n;i>=1;i--)
		c[i<<1]=c[i],c[i<<1|1]='$';
	c[1]='$';
	n=n<<1|1;lg[0]=-1;
	for(int i=1,r=0,mid=0;i<=n;i++){
		lg[i]=lg[i>>1]+1;
		if(i<=r)f[0][i]=min(f[0][(mid<<1)-i],r-i+1);
		while(i+f[0][i]<=n&&i-f[0][i]>=1&&c[i-f[0][i]]==c[i+f[0][i]])f[0][i]++;
		if(i+f[0][i]>r)r=i+f[0][i]-1,mid=i;
	}
	for(int i=1;i<=n;i++)f[0][i]--;
	for(int k=1;k<=20;k++)for(int i=1;i+(1<<k)-1<=n;i++)
		f[k][i]=max(f[k-1][i],f[k-1][i+(1<<(k-1))]);
	q=read();
	while(q--){
		int l=read()<<1,r=read()<<1;
		l--,r++;
		int L=1,R=(r-l+1)>>1,ans=0;
		while(L<=R){
			int mid=(L+R)>>1;
			if(query(l+mid-1,r-mid+1)>=mid)ans=max(ans,mid),L=mid+1;
			else R=mid-1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}