#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=5e5+10;
int n, factor[N], prime[N], pr; bool v[N];
void init()
{
    pr=0; memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0) prime[++pr]=i; factor[i]=i;
        for(int j=1;j<=pr && i*prime[j]<=n;j++)
        {
            v[i*prime[j]]=1; factor[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}
ULL f[N], d[N];
char s[N];
ULL Hash(int l, int r){return f[r]-f[l-1]*d[r-l+1];}
bool check(int l, int r, int len){return Hash(l, r-len)==Hash(l+len, r);}
int main()
{
    scanf("%d%s", &n, s+1);
    init();
    d[0]=1; for(int i=1;i<=n;i++) d[i]=d[i-1]*131;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*131+s[i];
    int q; scanf("%d", &q);
    while(q--)
    {
        int l, r, L; scanf("%d%d", &l, &r); L=r-l+1;
        for(int i=L; i>1; i=i/factor[i])
        {
            if(check(l, r, L/factor[i])) L=L/factor[i];
        }
        printf("%d\n", L);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=5e5+10;
int n,factor[N],prime[N],pr;bool v[N];
void init()
{
    pr=0;memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)prime[++pr]=i,factor[i]=i;
        for(int j=1;j<=pr && i*prime[j]<=n;j++)
        {
            v[i*prime[j]]=1;factor[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}
ULL f[N],d[N];
char s[N];
ULL Hash(int l,int r){return f[r]-f[l-1]*d[r-l+1];}
bool check(int l,int r,int len){return Hash(l,r-len)==Hash(l+len,r);}
int main()
{
    scanf("%d%s",&n,s+1);
    init();
    d[0]=1;for(int i=1;i<=n;i++)d[i]=d[i-1]*131;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*131+s[i];
    int q;scanf("%d",&q);
    while(q--)
    {
        int l,r,L;scanf("%d%d",&l,&r);L=r-l+1;
        for(int i=L;i>1;i=i/factor[i])
        {
            if( check(l,r,L/factor[i] )  )L=L/factor[i];
        }
        printf("%d\n",L);
    }
    return 0;
}