#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int Hash=29;
typedef unsigned long long ll;
int len,T;
ll mi[500005],ha[500005],g[500005];
bool flag[500005];
vector<int>pri;
char s[500005];
void prime(){
	for(int i=2;i<=len;i++){
		if(!flag[i]){
			pri.push_back(i);
			g[i]=i;
		}
		for(int j=0;j<pri.size()&&pri[j]*i<=len;j++){
			flag[pri[j]*i]=1;
			g[pri[j]*i]=pri[j];
			if(i%pri[j]==0)break;
		}
	}
}
ll cal(int x,int y){
//	cout<<"CaO"<<endl;	
	return (ha[y]-ha[x-1]*mi[y-x+1]%mod)%mod;
}
int main(){
	cin>>len;
	scanf("%s",s+1);
	cin>>T;
	prime();
//	for(int i=0;i<pri.size();i++)cout<<pri[i]<<" ";
//	cout<<endl;
//	for(int i=2;i<=len;i++)cout<<g[i]<<" ";
//	cout<<endl;
	mi[0]=1;
	for(int i=1;i<=len;i++){
		mi[i]=mi[i-1]*Hash%mod;
	}
	for(int i=1;i<=len;i++){
		ha[i]=(ha[i-1]*Hash+s[i]-'a'+1)%mod;
	}
	while(T--){
		int l,r;
		scanf("%d%d",&l,&r);
		int ans,lon;
		ans=lon=r-l+1;
		while(lon>1){
//			cout<<"C"<<l+ans/g[lon]<<" "<<r<<endl;
//			cout<<lon<<endl;
//			cout<<cal(l+ans/g[lon],r)<<" "<<cal(l,r-ans/g[lon])<<endl;
			if(cal(l+ans/g[lon],r)==cal(l,r-ans/g[lon])){
				ans/=g[lon];
			}
//			cout<<lon<<" "<<g[lon]<<endl;
			lon/=g[lon];
		}
		printf("%d\n",ans);
	}
	return 0;
}