#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll base=131;
const int N=1000010;
int n,q,l,r;
ll power[N],sum[N];
char s[N];
void init()
{
	power[0]=1;
	for(int i=1;i<=N-10;i++)
    	power[i]=power[i-1]*base;
}
void qq()
{
	sum[0]=0;
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]*base+(ll)(s[i]);
}
bool check(ll v,int k,int l,int r)
{
	for(int i=l;i<=r;i+=k)
	{
		if(v!=sum[i+k-1]-sum[i-1]*power[k]) return false;
	}
	return true;
}
int main()
{
	init();
	scanf("%d%s%d",&n,s+1,&q);
	qq();
	while(q--)
	{
		scanf("%d%d",&l,&r);
		for(int i=1;i<=r-l+1;i++)
		{
			if((r-l+1)%i!=0) continue;
			if(check(sum[l+i-1]-sum[l-1]*power[i],i,l,r)==true)
			{
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}

record