#include<bits/stdc++.h>
#include<cmath>
#define ll long long

using namespace std;
const int mod=1e9+7;
int has[500010],p[500010];
char s[500010];
int n,q;
vector<int >ys[500010];
ll read(){
	ll 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;
}


int main()
{
	n=read();
	p[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j*i<=n;j++) ys[j*i].push_back(i);
		sort(ys[i].begin(),ys[i].end());
	}
	for(int i=1;i<=n;i++) p[i]=(1ll*p[i-1]*131)%mod; 
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) has[i]=(1ll*has[i-1]*131+s[i])%mod;
	q=read();
	while(q--){
		int l=read(),r=read();
		int len=r-l+1;
		for(int i=0;i<ys[len].size();i++){
			int changdu=ys[len][i];
			int nowl=l,is=1;
			while(nowl<=r){
				if(((1ll*has[nowl+changdu-1]-(1ll*has[nowl-1]*p[changdu])%mod)+mod)%mod!=((1ll*has[l+changdu-1]-(1ll*has[l-1]*p[changdu])%mod)+mod)%mod){
					is=0;
					break;
				}
				nowl+=changdu;
			}
			if(is){
				cout<<changdu<<'\n';
				break;
			}
		}
	}
	return 0;
}

O2+卡常70pts