#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
	int sig = 1;
	ll num = 0;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') {
			sig = -1;
		}
		c = getchar();
	}
	while(isdigit(c)) {
		num = (num << 3) + (num << 1) + (c ^ 48);
		c = getchar();
	}
	return num * sig;
}
void Write(ll x) {
	if(x < 0) {
		putchar('-');
		x = -x;
	}
	if(x >= 10) {
		Write(x / 10);
	}
	putchar((x % 10) ^ 48);
}
const int N = 500005;
int f[N];
void Manacher(string s) {
	int i, n = s.size(), l = 0, r = -1;
	for(i = 0; i < n; i++) {
		int k = (i > r) ? 1 : min(f[l + r - i], r - i + 1);
		while(k <= i && i + k < n && s[i - k] == s[i + k]) {
			k++;
		}
		f[i] = k--;
		if(i + k > r) {
			l = i - k;
			r = i + k;
		}
	}
}
int lg[N];
void Init_lg(int n) {
	int i;
	for(i = 2; i <= n; i++) {
		lg[i] = lg[i >> 1] + 1;
	}
}
struct ST_Table {
	int f[25][N];
	void Init(int n, int a[]) {
		int i, j;
		for(i = 1; i <= n; i++) {
			f[0][i] = a[i];
		}
		for(j = 1; j <= lg[n]; j++) {
			for(i = 1; i + (1 << j) - 1 <= n; i++) {
				f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
			}
		}
	} 
	int Query(int l, int r) {
		int len = lg[r - l + 1];
		return max(f[len][l], f[len][r - (1 << len) + 1]);
	}
}st;
bool Check(int l, int r, int x) {
	int res = 0;
	if(x & 1) {
		res = st.Query(2 * (l + x / 2) - 1, 2 * (r - x / 2) - 1);
	}
	else {
		res = st.Query(2 * (l + x / 2 - 1), 2 * (r - x / 2));
	}
	return res >= x + 1;
}
int Solve(int ql, int qr) {
	int l = 0, r = qr - ql + 1, mid, res = 0;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(Check(ql, qr, mid)) {
			res = mid, l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	return res;
}
int main() {
	string s;
	cin >> s;
	Manacher(s);
	Init_lg(N - 5);
	string t = "$";
	int n = s.size(), i;
	for(i = 0; i < n; i++) {
		t.push_back(s[i]), t.push_back('$');
	}
	Manacher(t);
	st.Init(2 * n - 1, f);
	int q = Read();
	while(q--) {
		int l = Read(), r = Read();
		Write(Solve(l, r)), putchar('\n');
	}
	return 0;
}
/*
aaacbdccccadaadabbdbadcbcbbadcadb
6
5 22
1 18
15 33
1 33
8 12
15 27
 */