#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <ctime>
#include <set>
#include <map>
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

#define Darr(a, L, R) cerr << #a "[" << L << " ~ " << R << "] = "; rep(x, L, R) cerr << a[x] << " "; cerr << '\n';
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define D(x) (cerr << #x << " = " << x << '\n')
#define vit vector<int>::iterator
#define all(x) x.begin(), x.end()
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define chkmin(a, b) (a = min(a, b))
#define chkmax(a, b) (a = max(a, b))
#define sit set<int>::iterator
#define lowbit(x) (x & -x)
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pi acos(-1)
#define gc getchar
#define pc putchar
#define db double
#define y second
#define x first

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int mod = 998244353;
const int eps = 1e-9;

const int N = 2000010; int T = 1;
void print(int x) { dep(i, 20, 0) pc(((x >> i) & 1) ? '1' : '0'); }
int qpow(int a, int b = mod - 2, int s = 1) { for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) s = 1ll * s * a % mod; return s; }
namespace IO {
	void read() { return; }
	void write(char ch) { pc(ch); return; }
	void write() { return; }
	template <typename T> void read(T &x) { x = 0; T w = 0; char ch = gc(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = gc(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc(); x = w ? -x : x; }
	template <typename T> void print(T x) { if (!x) return; print<T>(x / 10), pc((x % 10) ^ '0'); }
	template <typename T> void write(T x) { if (x > 0) print<T>(x); else if (x < 0) pc('-'), print<T>(-x); else pc('0'); }
	template <typename T> void write(T x, char en) { write<T>(x), pc(en); }
	template <typename T, typename ...T2> void read(T &s, T2 &...oth) { read(s); read(oth...); return; }
}; using namespace IO;

const ULL P = 1331;
ULL p[N], h1[N], h2[N];
char str[N], s[N]; int st1[N][22], st2[N][22];
int n, q, len[N], lg[N];
ULL Hash1(int l, int r) { return 1ull * h1[r] - h1[l - 1] * p[r - l + 1]; }
ULL Hash2(int r, int l) { return 1ull * h2[l] - h2[r + 1] * p[r - l + 1]; }
void sub() {
	scanf("%s", str + 1);
	n = strlen(str + 1); rep(i, 1, n) s[i * 2] = str[i], s[i * 2 - 1] = '#';
	s[n * 2 + 1] = '#'; p[0] = 1ull; n = n * 2 + 1;
	rep(i, 1, n) h1[i] = 1ull * h1[i - 1] * P + 1ull * s[i];
	dep(i, n, 1) h2[i] = 1ull * h2[i + 1] * P + 1ull * s[i];
	rep(i, 1, n) p[i] = p[i - 1] * P;
//	cout << Hash1(1, 3) << ' ' << Hash2(3, 1) << endl; return;
	rep(i, 1, n) {
		int l = 0, r = min(i - 1, n - i);
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (Hash1(i - mid, i) == Hash2(i + mid, i)) l = mid;
			else r = mid - 1;
		} len[i] = l;
	} rep(i, 1, n) if (i & 1) st1[i][0] = len[i]; else st2[i][0] = len[i];
	rep(j, 1, 20) rep(i, 1, n) st1[i][j] = max(st1[i][j - 1], st1[i + (1 << j - 1)][j - 1]),
		st2[i][j] = max(st2[i][j - 1], st2[i + (1 << j - 1)][j - 1]);
	lg[1] = 0; rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
	auto qmax1 = [&](int l, int r) -> int {
		if (l == r) return len[l]; int d = r - l + 1, o = lg[d];
		return max(st1[l][o], st1[r - (1 << o) + 1][o]);
	};
	auto qmax2 = [&](int l, int r) -> int {
		if (l == r) return len[l]; int d = r - l + 1, o = lg[d];
		return max(st2[l][o], st2[r - (1 << o) + 1][o]);
	};
	auto query = [&](int L, int R) -> int {
		int l = 0, r = (R - L + 1);
		while (l < r) {
//			int mid = 3;
			int mid = l + r + 1 >> 1;
			int _l = 2 * L + mid - 1, _r = 2 * R - mid + 1;
//			D(_l), D(_r), D(mid); exit(0);
//			cout << qmax1(_l, _r) << ' ' << qmax2(_l, _r) << '\n'; exit(0);
			if (_l > _r) r = mid - 1;
			else if (qmax1(_l, _r) >= mid or qmax2(_l, _r) >= mid) l = mid;
			else r = mid - 1;
		} return l;
	};
//	cout << query(1, 3) << '\n'; return;
	read(q); while (q -- ) {
		int L, R; read(L, R);
		printf("%lld\n", query(L, R));
	} return;
}
signed main() {
	while (T -- ) sub();
	return 0;
}