#include<bits/stdc++.h>
using namespace std;

#define mod 998244353
#define maxn 500005

int n,q;
char S[maxn];
int hash[maxn];
vector<int>prime;
int min_prime_cause[maxn];
bool tag[maxn];
int pows[maxn];
void E(){
	for(int i=2;i<=n;i++){
		if(!tag[i])
			prime.push_back(i),min_prime_cause[i]=i;
		for(int j=0;j<prime.size()&&prime[j]*i<=n;j++){
			tag[prime[j]*i]=1;
			min_prime_cause[prime[j]*i]=prime[j];
			if(i%prime[j]==0)break;
		}
	}
}
int get(int l,int r){
	return ((hash[r]-hash[l-1]*pows[r-l+1])%mod+mod)%mod;
}
int main(){
	cin>>n;
	E();
	scanf("%s",S+1);
	for(int i=1;i<=n;i++){
		hash[i]=(hash[i-1]*13+S[i]-'a'+1)%mod;
	}
	pows[0]=1;
	for(int i=1;i<=n;i++){
		pows[i]=(pows[i-1]*13)%mod;
	}
	cin>>q;
	while(q--){
		int l,r,len,ans;
		cin>>l>>r;
		ans=len=r-l+1;
		if(get(l+1,r)==get(l,r-1)){
			cout<<1<<'\n';
			continue;
		}
		while(len>1){
			if(get(l+ans/min_prime_cause[len],r)==get(l,r-ans/min_prime_cause[len])){
				ans/=min_prime_cause[len];
			}
			len/=min_prime_cause[len];
		}
		cout<<ans<<'\n';
	}
	return 0;
}