求卡空间

/* ChongYun */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define File(s,t) freopen(s".in","r",stdin),freopen(t".out","w",stdout)
#define Time() cerr<<fixed<<setprecision(6)<<1.*(double)(clock()-__st)/CLOCKS_PER_SEC<<"s\n"
#define Memory() cerr<<fixed<<setprecision(6)<<1.*fabs(&__t-&__s)/1024./1024.<<"MB\n"

#define Find(S,x) (S.find(x)!=S.end())
#define umap __gnu_pbds::gp_hash_table

char __s; clock_t __st;
#define ll long long
#define ldb long double
#define ull unsigned long long
#define reg register

using namespace std;

#define pii pair<int,int>
#define fir first
#define sec second

#define _LIMIT(x) (x>='a'&&x<='z')
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline char gc(){ reg char ch=getchar();while(!_LIMIT(ch))ch=getchar();return ch; }

inline int read(){
	reg int x=0,f=1;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x*f;
}
inline int read(string &s){
	s=""; reg char ch=getchar();
    while(!_LIMIT(ch)) ch=getchar();
    while(_LIMIT(ch)) s+=ch,ch=getchar();
	return (int)s.size();
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar((x%10)^48);
}
inline void write(int x,char ch){ write(x),putchar(ch); }
inline void write(string s){  for(char ch:s) putchar(ch); }
struct Flush{ ~Flush(){ flush(); } }_;
const int N=5e5+5;
int n,id[N][20],Hsh[N][20];
string s;
umap<ull,int> mp;
umap<int,int> pred[N][2],succ[N];
int flg[N];
ull base(131),Hash[N][20],pw[N];
inline void init(){
    for(int i=1;i<=n;++i) Hash[i][0]=s[i];
    pw[0]=1;
    for(int i=1;i<=n;++i) pw[i]=pw[i-1]*base;
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            Hash[i][j]=Hash[i][j-1]*pw[1<<j-1]+Hash[i+(1<<j-1)][j-1];
        }
    }
    for(int j=0,idx=0;(1<<j)<=n;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            if(!Find(mp,Hash[i][j])) mp[Hash[i][j]]=++idx;
            Hsh[i][j]=mp[Hash[i][j]];
        }
    }
    for(int i,j=0,idx=1;(1<<j)<=n;++j){
        for(i=1;i+(1<<j)-1<=n;i+=(1<<j),++idx){
            for(int k=i;k<=i+(1<<j)-1;++k){
                id[k][j]=idx;
                if(!Find(pred[idx][0],Hsh[k][j])) pred[idx][0][Hsh[k][j]]=k;
                else if(!Find(pred[idx][1],Hsh[k][j])) pred[idx][1][Hsh[k][j]]=k;
                succ[idx][Hsh[k][j]]=k;
            }
        }
        if(i<=n) ++idx;
        for(;i<=n;++i) id[i][j]=idx;
    }
}
struct Node{ int l,r,d; };
inline Node f(int i,int x){
    if(!Find(pred[i][0],x)) return {-1,-1,-1};
    if(!Find(pred[i][1],x)) return {pred[i][0][x],succ[i][x],succ[i][x]-pred[i][0][x]};
    return {pred[i][0][x],succ[i][x],pred[i][1][x]-pred[i][0][x]};
}
inline int nxt(int i,int j,int x){
    Node p=f(id[i][j],x);
    if(p.r<i||p.d==-1) p=f(id[i][j]+1,x);
    if(p.d==-1) return -1;
    if(!p.d) return p.l;
    return (i<=p.l?p.l:p.l+(i-p.l+p.d-1)/p.d*p.d);
}
inline int pre(int i,int j,int x){
    Node p=f(id[i][j],x);
    if(p.l>i||p.d==-1) p=f(id[i][j]-1,x);
    if(p.d==-1) return -1;
    if(!p.d) return p.l;
    return (p.r<=i?p.r:p.l+(i-p.l)/p.d*p.d);
}
inline Node query(int l,int r,int L,int R,int i,int op){
    int k,u,v;
    if(!op){
        k=nxt(r-R+1,i,Hsh[l][i]);
        if(k==-1) return {-1,-1,-1};
        u=nxt(k+1,i,Hsh[l][i]);
        if(u==-1) return {r-k+1,r-k+1,0};
        v=pre(r-L+1,i,Hsh[l][i]);
        return {r-v+1,r-k+1,u-k};
    }else{
        k=nxt(l,i,Hsh[r-L+1][i]);
        if(k==-1) return {-1,-1,-1};
        u=nxt(k+1,i,Hsh[r-L+1][i]);
        if(u==-1) return {k-l+L,k-l+L,0};
        v=pre(l+R-L,i,Hsh[r-L+1][i]);
        return {k-l+L,v-l+L,u-k}; 
    }
}
inline int Merge(Node S,Node T){
    if(S.d==T.d){
        if(!S.d) return (S.l==T.l?S.l:-1); 
        if(S.l%S.d!=T.l%T.d) return -1;
        if(S.r<T.l||T.r<S.l) return -1;
        return min(S.r,T.r);
    }
    if(S.d<0||T.d<0) return -1;
    if(!S.d){
        if(T.l<=S.l&&S.l<=T.r&&(S.l-T.l)%T.d==0) return S.l;
        return -1;
    }
    if(!T.d){
        if(S.l<=T.l&&T.l<=S.r&&(T.l-S.l)%S.d==0) return T.l;
        return -1;
    }
    for(int i=S.l;i<=S.r;i+=S.d) flg[i]=1;
    int res(-1);
    for(int i=T.l;i<=T.r;i+=T.d) if(flg[i]) res=max(res,i);
    for(int i=S.l;i<=S.r;i+=S.d) flg[i]=0;
    return res;
}
inline int solve(int l,int r){
    for(int i=__lg(r-l+1);i>=1;--i){
        int L(1<<i),R(min((1<<i+1),r-l+1)-1);
        if(L>R) continue;
        Node S=query(l,r,L,R,i,0);
        Node T=query(l,r,L,R,i,1);
        if(S.d==-1||T.d==-1) continue;
        int res=Merge(S,T);
        if(res!=-1) return res; 
    }
    if(s[l]==s[r-1]&&s[l+1]==s[r]&&l+1<r) return 2;
    if(s[l]==s[r]&&l!=r) return 1;
    return 0;
}
namespace Tracy{
    inline void Main(){
        n=read(s),s=' '+s,init();
        for(int q=read(),l,r;q;q--){
            l=read(),r=read();
            write(solve(l,r),'\n');
        }
    }
	char __t;
    inline int Reznik(int T=1){
        __st=clock();
	    while(T--) Main();
	    return /*Time(),Memory(),*/0;
    }
}

signed main(){ 
	// File("","");
	return Tracy::Reznik(); 
}