#include<bits/stdc++.h>
#define ll long long
#define pii make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=b;i>=a;--i)
using namespace std;
inline ll read() {
	ll x=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9') {
		if (c=='-')  f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void print(ll x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
inline void pprint(ll x) {
	print(x);
	puts("");
}
const int N = 1e6 + 7;
ll Nxt[N << 1], to[N << 1], head[N], cnt = 1;
void add(int x, int y) {
	Nxt[++cnt] = head[x];
	to[cnt] = y;
	head[x] = cnt;
}
char s[N];
ll son[N], siz[N], dep[N], fa[N], top[N], rnk[N], dfn[N], tot = 0;
void dfs1(int x) {//son dep fa siz;
	son[x] = -1;
	siz[x] = 1;
	for(int i = head[x]; i; i = Nxt[i])
		if (!dep[to[i]]) {
			dep[to[i]] = dep[x] + 1;
			fa[to[i]] = x;
			dfs1(to[i]);
			siz[x] += siz[to[i]];
			if (son[x] == -1 || siz[to[i]] > siz[son[x]])
				son[x] = to[i];
		}
}

void dfs2(int x, int t) {//dfn rnk top
	top[x] = t;
	tot++;
	dfn[x] = tot;
	rnk[tot] = x;
	if (son[x] == -1)
		return;
	dfs2(son[x], t);  // 优先对重儿子进行 DFS，可以保证同一条重链上的点 DFS 序连续
	for (int i = head[x]; i; i = Nxt[i])
		if (to[i] != son[x] && to[i] != fa[x])
			dfs2(to[i], to[i]);
}
ll lca(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) {
			x = fa[top[x]];
		} else {
			y = fa[top[y]];
		}
	}
	return dep[x] < dep[y] ? x : y;
}
ll f[N], nxt[N];
void get_nxt(char *t) {
	int m = strlen(t + 1);
	nxt[1] = 0;
	for(int i = 2, j = 0; i <= m; ++i) {
		while(j > 0 && t[i] != t[j + 1]) j = nxt[j];
		if(t[i] == t[j + 1]) ++j;
		nxt[i] = j;
	}
}
int n;
ll vis[N];
void build(int n) {
	for(int i = 1; i <= n; ++i) {
		int j = i;
		while(j > 0 && !vis[j]) {
			add(j, nxt[j]);
			add(nxt[j], j);
			vis[j] = 1;
			j = nxt[j];
		}
	}
	dep[0] = 1;
	dfs1(0);
	dfs2(0, 0);
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	get_nxt(s);
	build(n);
	int q = read();
	while(q--) {
		int x = read(), y = read();
		pprint(lca(nxt[x], nxt[y]));
	}
	return 0;
}