#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using std::cin;using std::cout;
constexpr int N=1000005;
std::string s;
int n,q,l,r,p[N];
bool tag=1;
signed main(){
//	freopen("palindrome.in","r",stdin);
//	freopen("palindrome.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>s>>q;n=s.size();s=" "+s;
	for(int i=1;i<=n;++i) if(s[i]!='a'){tag=0;break;}
	if(tag){for(int i=1;i<=q;++i){cin>>l>>r;cout<<r-l+1<<'\n';}return 0;}
	if(n<=5000&&q<=5000){
		for(int i=1;i<=q;++i){
			cin>>l>>r;std::string t="#$";
			for(int j=l;j<=r;++j){t+=s[j];t+='$';};t+="@";
			int m=2*(r-l+1),ans=0;
			for(int j=0;j<=m;++j) p[j]=0;
			for(int j=1,mid=1,r=0;j<=m;++j){
				if(j<=r) p[j]=std::min(p[2*mid-j],r-j);
				while(t[j+p[j]]==t[j-p[j]]) ++p[j];
				if(j+p[j]>r){mid=j;r=j+p[j];}
				ans=std::max(ans,p[j]);
			}
			cout<<ans-1<<'\n';
		}
		return 0;
	}
	cout<<"明堂院树";
	return 0;
}//第四十回 史太君两宴大观园 金鸳鸯三宣牙牌令
//明堂院树