#28 和 #30 TLE,
求大佬优化

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5; 
int n,q,l,r; 
string s;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
struct Hash{
	int sed,mod,hsh[N]={0},po[N]={1};
	void init(int sed_in,int mod_in){
		sed=sed_in,mod=mod_in;
		for(int i=1;i<N;i++) po[i]=po[i-1]*sed%mod;
	}
	void gethsh(string s){
		for(int i=0;i<s.size();i++) hsh[i+1]=(hsh[i]*sed%mod+s[i])%mod;
	}
	int query(int l,int r){
		return (hsh[r]-hsh[l-1]*po[r-l+1]%mod+mod)%mod;
	}
}h1;
int st[N],pr[N],p[N],cnt;
void olpri(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]) pr[++cnt]=i,p[i]=i;
		for(int j=1;i*pr[j]<=n;j++){
			st[i*pr[j]]=1;
			p[i*pr[j]]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
}
signed main(){
    n=read();
	cin>>s;
	olpri(n);
	h1.init(128,1000000007);
    h1.gethsh(s);
    q=read();
    while(q--){
    	l=read();
        r=read();
    	int len=(r-l+1);
    	int ans=len;
    	if(h1.query(l+1,r)==h1.query(l,r-1)){
    		cout<<1<<'\n';
    		continue;
		}
    	while(len>1){
    		if(h1.query(l+ans/p[len],r)==h1.query(l,r-ans/p[len])) ans/=p[len];
    		len/=p[len];
		}
		cout<<ans<<'\n';
	}
	return 0;
}