#include<iostream>
#include<cstdio>
#include<cstring>
#define ull unsigned long long int
using namespace std;
const int HASH=1000000009;
int n;
char s[500005];
ull Hash[500005];
ull power[500005];
int prime[100005];
bool num[500005];
int min_num[500005];
void init()
{
	power[0]=1;
	for(int i=1;i<=n;i++)
	{
		power[i]=power[i-1]*HASH;
	}
	for(int i=1;i<=n;i++)
	{
		Hash[i]=Hash[i-1]*HASH+(ull)s[i];
	}
	prime[1]=1;
	prime[0]=1;
	for(int i=2;i<=n;i++)
	{
		if(num[i]==0)
		{
			prime[0]++;
			prime[prime[0]]=i;
		}
		for(int q=2;prime[q]*i<=n&&q<=prime[0];q++)
		{
			num[prime[q]*i]=1;
			min_num[prime[q]*i]=prime[q];
			if(i%prime[q]==0)
				break;
		}
	}
}
ull hash_get(int start,int end)
{
	return Hash[end]-Hash[start-1]*power[end-start+1];
}

int work(int start,int end,int length)
{
	int ans=length;
	if(hash_get(start,end-length)==hash_get(start+length,end))
	{
		if(min_num[length]==0)
		{
			return ans;
		}
		else
		{
			int tmp=min_num[length];
			int ans1,ans2;
			ans1=work(start,end,tmp);
			ans2=work(start,end,length/tmp);
			ans=min(min(ans,ans1),ans2);
			return ans;	
		}
	}
	else
	{
		return 999999999;
	}
}
int main()
{
	int q=0;
	scanf("%d",&n);
	scanf("%s",s+1);
	init();
	scanf("%d",&q);
	while(q--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(work(a,b,1)==1)
		{
			printf("1\n");
			continue;
		}
		printf("%d\n",work(a,b,b-a+1));
	}
	return 0;
}