#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10 , Q = 5e5 + 10 , T = 21 * N , C = 26;
int n , m , q , len[N] , id[N] , rt[Q] , ans[Q]; 
struct Query{int l , r , id;}qu[Q] , tmp[Q];
vector<int>pos[C];
string t; char s[N];
class fastIO{private:char ibuf[50007],*p1=ibuf,*p2=ibuf,obuf[50007],*p3=obuf,sta[50];bool file_end=false;char get(){return p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,50007,stdin),p1==p2)?(file_end=true),char(EOF):*p1++;}void put(const char x){p3-obuf<50007?*p3++=x:(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x);}public:explicit operator bool(){return!file_end;}size_t flush(){size_t f=fwrite(obuf,p3-obuf,1,stdout);p3=obuf;*p3=0;return f;}fastIO&operator>>(char&t){for(t=get();!isgraph(t);t=get());return*this;}template<typename any>typename std::enable_if<std::is_same<any,char>::value,any>::type tpval(){char t;for(t=get();!isgraph(t);t=get());return t;}fastIO&operator>>(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}fastIO&operator>>(std::string&t){t.clear();char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return*this;}template<typename any>typename std::enable_if<std::is_same<any,std::string>::value,any>::type tpval(){std::string t;char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return t;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator>>(any&t){t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,any>::type tpval(){any t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return t;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator>>(any&t){t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,any>::type tpval(){any t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return t;}template<typename any1,typename any2>fastIO&operator>>(std::pair<any1,any2>&t){return*this>>t.first>>t.second;}template<typename any1,typename any2>std::pair<any1,any2>tpval(){return std::pair<any1,any2>(tpval<any1>(),tpval<any2>());}template<typename any>fastIO&read(any&t){return*this>>t;}fastIO&read(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}template<typename any,typename...args>fastIO&read(any&t1,args&...t2){return(*this>>t1).read(t2...);}fastIO&operator<<(const char t){put(t);return*this;}fastIO&operator<<(const char*t){for(;*t;t++)put(*t);return*this;}fastIO&operator<<(const std::string&t){for(const char it:t)put(it);return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;if(t<0)t=-t,put(45);while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any1,typename any2>fastIO&operator<<(const std::pair<any1,any2>&t){return*this<<t.first<<' '<<t.second;}template<typename any>fastIO&write(const any&t){return*this<<t;}template<typename any,typename...args>fastIO&write(const any&t1,const args&...t2){return(*this<<t1).write(t2...);}~fastIO(){fwrite(obuf,p3-obuf,1,stdout);}}fio;
struct Segtree
{
	int tot;
	struct Node{int lc , rc;}tr[T];
	#define lc(p) (tr[p].lc)
	#define rc(p) (tr[p].rc)
	int update(int s , int p , int l = 1 , int r = n)
	{
		int q = ++tot;
		tr[q] = tr[p];
		if(l == r)return q;
		int mid = (l + r) >> 1;
		if(s <= mid)lc(q) = update(s , lc(p) , l , mid);
		else rc(q) = update(s , rc(p) , mid + 1 , r);
		return q;
	}
	bool query(int s , int e , int p , int l = 1 , int r = n)
	{
		if(!p || (s <= l && r <= e))return p;
		int mid = (l + r) >> 1;
		if(s <= mid){if(query(s , e , lc(p) , l , mid))return 1;}
		if(mid < e){if(query(s , e , rc(p) , mid + 1 , r))return 1;}
		return 0;
	}
}sgt;
void Calc(int l , int r , int ql , int qr)
{
	if(l > r || ql > qr)return ;
	// cerr << "Calc " << l << ',' << r << " " << ql << ',' << qr << "\n";
	if(l == r)
	{
		for(int i = ql ; i <= qr ; i++)
		{
			auto [x , y , id] = qu[i];
			ans[id] = l;
		}
		return ;
	}
	int mid = (l + r + 1) >> 1 , hd = ql , tl = qr;
	// cerr << "  mid = " << mid << "\n";
	for(int i = ql ; i <= qr ; i++)
	{
		auto [x , y , id] = qu[i];
		int L = x + mid - 1 , R = y - mid + 1;
		// cerr << "\t(" << x << ',' << y << ' ' << id << "): [" << L << ',' << R << "]" << (L > R ? 0 : sgt.query(L , R , rt[mid])) << "\n";
		if(L > R || !sgt.query(L , R , rt[mid]))
			tmp[hd++] = qu[i];
		else tmp[tl--] = qu[i];
	}
	for(int i = ql ; i <= qr ; i++)qu[i] = tmp[i];
	Calc(l , mid - 1 , ql , hd - 1);
	Calc(mid , r , tl + 1 , qr);
}
signed main()
{
	fio >> t >> q; n = t.size();
	if(count(t.begin() , t.end() , 'a') == n)
	{
		for(int i = 1 ; i <= q ; i++)
		{
			int l , r; fio >> l >> r;
			fio << r - l + 1 << "\n";
		}
		return 0;
	}
	for(int i = 1 ; i <= n ; i++)
		pos[t[i - 1] - 'a'].push_back(i);
	for(int i = 1 ; i <= n * 2 ; i += 2)
		s[i] = t[i / 2] , s[i + 1] = '#';
	s[n = n * 2 + 1] = '#';
	int L = n , R = 1;
	for(int i = 1 ; i <= q ; i++)
	{
		int l , r; fio >> l >> r;
		char ch = t[l - 1];
		if(ch == t[r - 1])
		{
			vector<int>&vc = pos[ch - 'a'];
			auto il = lower_bound(vc.begin() , vc.end() , l);
			auto ir = upper_bound(vc.begin() , vc.end() , r);
			if(ir - il == r - l + 1)
				ans[i] = r - l + 1;
		}
		if(!ans[i])
		{
			qu[++m] = {l * 2 - 1 , r * 2 + 1 , i};
			L = min(l * 2 - 1 , L);
			R = max(R , r * 2 + 1);
		}
	}
	if(m)
	{
		for(int i = 1 , l = 0 , r = 0 ; i <= n ; i++)
		{
			if(l <= i && i <= r)
				len[i] = min(r - i , len[l + r - i]);
			while(i - len[i] > 1 && i + len[i] < n && s[i - len[i] - 1] == s[i + len[i] + 1])
				len[i]++;
			if(i + len[i] > r)l = i - len[i] , r = i + len[i];
		}
		// for(int i = 1 ; i <= n ; i++)cerr << s[i];
		// cerr << "\n";
		// for(int i = 1 ; i <= n ; i++)cerr << len[i] << " \n"[i == n];
		for(int i = 1 ; i <= R - L + 1 ; i++)id[i] = L + i - 1;
		sort(id + 1 , id + (R - L + 1) + 1 , [&](int x , int y){return len[x] > len[y];});
		int md = len[id[1]] + 1;
		for(int i = md , j = 1 ; i >= 0 ; i--)
		{
			rt[i] = rt[i + 1];
			for(; j <= R - L + 1 && len[id[j]] >= i ; j++)
				rt[i] = sgt.update(id[j] , rt[i]);
			// cerr << "d = " << i << ":";
			// for(int j = 1 ; j <= n ; j++)cerr << sgt.query(j , j , rt[i]) << " \n"[j == n];
		}
		// auto t1 = chrono::steady_clock::now();
		Calc(0 , md , 1 , m);
		// auto t2 = chrono::steady_clock::now();
		// cerr << (t2 - t1) / 1ms << "ms\n";
	}
	for(int i = 1 ; i <= q ; i++)
		fio << ans[i] << "\n";
	return 0;
}