C++ :

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
# include <vector>
using namespace std;
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i) 
# define REP(i, n) FOR (i, 1, n)
# define REP_0(i, n) FOR (i, 0, n - 1)
# define REP_D(i, n) DWN (i, 1, n)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define SR 401000
# define w0 first
# define w1 second
typedef pair <int, int> pii;
const int inf = 1 << 30;
struct Edge { int y, frt; void set (int yr, int fr) { y = yr, frt = fr; } } g[SR];
struct Sam { int tr[26], par, l; Sam () { memset (tr, -1, sizeof (tr)); } } sam[SR];
struct Seg { int lc, rc; pii max; } t[SR << 2];
int n, m, r0, r1, ssz, lst, tsz, pos[SR], gsz, dsz, son[SR], sz[SR], fa[SR], top[SR], bot[SR], dn[SR], ed[SR], nd[SR], lq[SR], rq[SR], ans[SR];
bool del[SR]; char s[SR]; vector <pii> qy[SR];
priority_queue <pii> Q[SR << 2];
# define v g[i].y
int bt (int x) {
	dn[x] = ++ dsz; int z = x;
	if (son[x]) top[son[x]] = top[x], z = bt (son[x]);
	REP_G (i, x) if (v != fa[x] && v != son[x]) top[v] = v, bt (v);
	ed[x] = dsz;
	return bot[x] = z;
}
void pre (int x) {
	sz[x] = 1;
	REP_G (i, x) if (v != fa[x]) {
		fa[v] = x, pre (v), sz[x] += sz[v];
		if (sz[son[x]] < sz[v]) son[x] = v;
	}
}
pii get_top (int x) {
	for (; !Q[x].empty () && del[Q[x].top ().w1]; Q[x].pop ());
	return Q[x].empty () ? pii () : Q[x].top ();
}
# define u t[x]
# define ulfc t[u.lc]
# define urtc t[u.rc]
void seg_ins (int &x, int l, int r, int p, const pii &w) {
	if (!x) x = ++ tsz;
	if (l == r) { if (w.w1 != -1) Q[x].push (w); u.max = get_top (x); return; }
	int mid = (l + r) >> 1;
	p <= mid ? seg_ins (u.lc, l, mid, p, w) : seg_ins (u.rc, mid + 1, r, p, w);
	u.max = max (ulfc.max, urtc.max);
}
pii seg_max (int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return u.max;
	int mid = (l + r) >> 1; pii z;
	if (ql <= mid) z = max (z, seg_max (u.lc, l, mid, ql, qr));
	if (qr > mid) z = max (z, seg_max (u.rc, mid + 1, r, ql, qr));
	return z;
}
# define fx top[x]
# undef u
# undef v
# define u sam[x]
# define o sam[y]
# define w sam[z]
# define v u.tr[c]
# define vn sam[v]
void extend (int c) {
	int x = lst, z = ++ ssz; lst = z, w.l = u.l + 1;
	for (; x != -1 && v == -1; x = u.par) v = z;
	if (x == -1) w.par = 1;
	else if (u.l + 1 == vn.l) w.par = v;
	else {
		int y = ++ ssz, _v = v;
		o = vn, o.l = u.l + 1, w.par = vn.par = y;
		for (; x != -1 && v == _v; x = u.par) v = y;
	}
}
# undef w

void ins_query (int x, int l, int id) { for (; x; x = fa[fx]) seg_ins (r0, 1, dsz, dn[x], pii (l + u.l - 1, id)), seg_ins (r1, 1, dsz, dn[x], pii (l, id)); }
void del_query (int id) {
	del[id] = true;
	for (int x = nd[rq[id]]; x; x = fa[fx]) seg_ins (r0, 1, dsz, dn[x], pii (-1, -1)), seg_ins (r1, 1, dsz, dn[x], pii (-1, -1));
}
void ins_node (int x, int c) {
	if (x == 1) return;
	pii tz;
	for (; c - u.l + 1 <= (tz = seg_max (r1, 1, dsz, dn[x], ed[x])).w0 && tz.w1; del_query (tz.w1)) ans[tz.w1] = c - lq[tz.w1] + 1;
	for (; x; x = fa[fx]) {
		for (; c <= (tz = seg_max (r0, 1, dsz, dn[fx], dn[x])).w0 && tz.w1; del_query (tz.w1)) ans[tz.w1] = c - lq[tz.w1] + 1;//, printf ("%d\n", tz.w1);
		for (; c - u.l + 1 <= (tz = seg_max (r1, 1, dsz, dn[x], dn[bot[x]])).w0 && tz.w1; del_query (tz.w1)) ans[tz.w1] = c - lq[tz.w1] + 1;
	}
}
void AE (int x, int y) { g[++ gsz].set (y, pos[x]), pos[x] = gsz; }
#include <cassert>
int main () {
	//freopen ("B.in", "r", stdin);
	//freopen ("B.out", "w", stdout);
	scanf("%s%d", s + 1, &m); n = strlen(s + 1);
	int l, r; sam[lst = ssz = 1].par = -1;
	REP (i, n) extend (s[i] - 'a'), nd[i] = lst;
	REP (i, m) scanf ("%d%d", &l, &r), qy[r].push_back (pii (l, i)), lq[i] = l, rq[i] = r;
	FOR (x, 2, ssz) AE (u.par, x);
	pre (1), top[1] = 1, bt (1);
	REP_D (i, n) {
		ins_node (nd[i], i);
		for (pii w : qy[i]) ins_query (nd[i], w.w0, w.w1);
	}
	REP (i, m) {
		printf ("%d\n", ans[i]);
	//	assert(2 * ans[i] >= (rq[i] - lq[i] + 1));
	}
	return 0;
}