#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int n;
string s;
int q,a,b;
ULL pp=13331;
ULL p[1000001];
ULL hsh[1000001];
int g[1000001];
int v[1000001];
void f(){
	for(int i=2;i<=n;i++){
		if(!g[i]){
			g[i]=i;
			for(int j=i;i*j<=n;j++){
				g[i*j]=i;
			}
		}
	}
}
ULL get(int x,int y){
	return hsh[y]-hsh[x-1]*p[y-x+1];
}
int main(){
	cin>>n>>s>>q;
	s=" "+s;
	f();
	p[0]=1;
	for(int i=1;i<=n;i++){
		hsh[i]=hsh[i-1]*pp+s[i];
		p[i]=p[i-1]*pp;
	}
	while(q--){
		cin>>a>>b;
		int len=b-a+1;
		int cnt=0,ans=len;
		while(len!=1){
			v[++cnt]=g[len];
			len=len/g[len];//依次找len的质因数 
		}len=b-a+1; 
		for(int j=1;j<=cnt;j++){//逐渐缩小长度 
			int ans=len/v[j];
			if(get(a,b-ans)==get(a+ans,b)) len=ans;
		}printf("%d\n",len);
	}
	return 0;
}