#include<bits/stdc++.h>
using namespace std;
const unsigned int mod=1007;
const int N=5e5+5,P=29;
char st[N];
int n,q,l,r,tot;
int p[N],h[N],f[N],flag[N],g[N];
void initHash(){
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=p[i-1]*P,p[i]%=mod;
	for(int i=1;i<=n;i++)h[i]=(h[i-1]*P+st[i]-'a'+1)%mod;
}
void initPrime(int x){
	for(int i=2;i<=x;i++){
		if(flag[i]==0)f[++tot]=i,g[i]=i;
		for(int j=1;j<=tot&&f[j]*i<=n;j++){
			flag[f[j]*i]=1;
			g[f[j]*i]=f[j];
			if(i%f[j]==0)break;
		}
	}
}
int Hash(int l,int r){
	return ((h[r]-h[l-1]*p[r-l+1])%mod+mod)%mod;
}
int main(){
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++){
		scanf("%c",&st[i]);
	}
	initPrime(n);
	initHash();
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);
		int len=r-l+1;
//		for(int j=0;j<len;j++){
//			if(len%(j+1)!=0)continue;
//			if(Hash(l+j,r)==Hash(l,r-j)){
//				printf("%d\n",j);
//				break;
//			}
//		}
		if(Hash(l+1,r)==Hash(l,r-1)){
			printf("1\n");
			continue;
		}
		int L=len;
		while(len>1){
			if(Hash(l+L/g[len],r)==Hash(l,r-L/g[len]))L/=g[len];
			len/=g[len];
		}
		printf("%d\n",L);
	}
}