#include <bits/stdc++.h>
using namespace std;
#define qc ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
typedef pair<int, int> Pair;
typedef unsigned long long ull;
const int N=5e5+5;
const int P=13331;
string s;
ull h[N], p[N]; // 
void init(string s,int n){
p[0]=1;
for(int i=1;i<=n;i++){
    h[i]=h[i-1]*P+s[i];
    p[i]=p[i-1]*P;
    }
}
 
ull get(int l, int r){
    return h[r]-h[l-1]*p[r-l+1];
}
bool check(int l,int r,int len){
    return get(l+len,r)==get(l,r-len);
}
vector<int> primes;
bool prime[N];

void ini(int n) {
    fill(prime,prime+n+1,1);
    for(int i=2; i<=n; i++) {
        if(prime[i])
            primes.pb(i);
        for(auto p:primes) {
            if(p*i<=n)
                prime[p*i]=0;
            if(p*i>n||i%p==0)
                break;
        }
    }
}
signed main() {
    qc;
    int n;
    cin>>n;
    primes.pb(1);
    ini(n+1);
    vector<int>yinzi[n+1];
    for(auto i:primes){
        int now=i;
        while(now<=n){
            yinzi[now].pb(i);
            now+=i;
        }
    }
    rep(i,1,n) yinzi[i].pb(i);
    cin>>s;
    s=' '+s;
    init(s,n);
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        for(auto it:yinzi[len]){
            if(check(l,r,it)){
                cout<<it<<"\n";
                break;
            }
        }
    }
}