#include<bits/stdc++.h>
using namespace std;
char s[1000005],t[1000005];int n,q;
int st[1000005][21];
int pi[1000005];
int lg[2100005];
inline int read(){
	int x = 0;char c = getchar();
	while(c<'0' or c>'9')c = getchar();
	while('0'<=c and c<='9'){
		x = x*10+(c^48);c = getchar();
	}return x;
}
inline query(int l,int r){
	int k = lg[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int mid,int l,int r){
	int rr = r-mid+1,ll = l+mid-1;
	//cout << " " << ll << ' ' <<rr << endl;
	if(ll>rr)return 0;
	//cout << ' ' <<ll << " " << rr << " " <<query(ll,rr) << " " << mid << endl;
	return (query(ll,rr)>=mid);
}
int l,r;
signed main(){
	for(int i =0;i<=20;i++){
		for(int j =(1<<i);j<(1<<i+1);j++){
			lg[j] = i;
		}
	}
	scanf("%s",t+1);n = strlen(t+1);
	for(int i = 1;i<=n;i++)s[2*i-1] = '#',s[2*i] = t[i];
	s[2*n+1] = '#';n = 2*n+1; 
	
	for(int i = 1;i<=n;i++){
		if(i<=r){
			pi[i] = min(r-i+1,pi[l+r-i]);
		}
		while(i+pi[i]<=n and i-pi[i]>0 and s[i+pi[i]] == s[i-pi[i]])++pi[i];
		if(i+pi[i]-1>r){
			l= i-pi[i]+1,r = i+pi[i]-1;
		}
	}
	for(int i = 1;i<=n;i++)st[i][0] = pi[i];
	for(int i = 1;i<=20;i++){
		for(int j = 1;j+(1<<i)-1<=n;j++){
			st[j][i] = max(st[j][i-1],st[j+(1<<i-1)][i-1]);
		}
	}
//	for(int i = 1;i<=n;i++)cout << s[i] << ' ';cout << endl;
//	for(int i = 1;i<=n;i++)cout << pi[i] << ' ';cout << endl;
//	cout << query(1,9) << endl;
//	return 0;
	q = read();
	while(q--){
		int l,r;cin >> l >> r;
		l = 2*l-1,r = 2*r+1;
		int ll = 1,rr = (r-l+3)/2;
	//	cout << ll << " " << rr << endl;
		while(ll<rr){
			int mid = ll+rr+1>>1;
		//	cout<< mid << endl;
			if(check(mid,l,r))ll = mid;
			else rr = mid-1;
		}//cout << " " << check(5,l,r) << ' ' << check(6,l,r) << endl;
		printf("%d\n",ll-1);
	}
	return 0;
}/*
故事的小黄花。 
acabcba
5
1 3
1 5
2 7
3 7
4 7
aaacbdccccadaadabbdbadcbcbbadcadb
6
5 22
1 18
15 33
1 33
8 12
15 27
*/

answer.code:14:8: error: ISO C++ forbids declaration of ‘query’ with no type [-fpermissive]
   14 | inline query(int l,int r){
      |        ^~~~~
answer.code: In function ‘int main()’:
answer.code:32:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |         scanf("%s",t+1);n = strlen(t+1);
      |         ~~~~~^~~~~~~~~~