#include <bits/stdc++.h>
#define int unsigned long long 
using namespace std;
const int p=1331;
const int N=5e5+5;
int n,q,a[N],pri[N],cnt,ys[N],y[N];
string s;
bool f[N];
inline void init()
{
    for(int i=2;i<=n;i++)
    {
        if(!f[i])
        {
            pri[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++)
        {
            f[i*pri[j]]=true;
            if(i%pri[j]==0) break; 
        }
    }
    y[0]=1;
    for(int i=1;i<=n;i++)
    {
        y[i]=y[i-1]*p;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]*p+s[i-1];
    }
}
inline bool check(int x,int c,int start)
{
    int fs=a[start+c-1]-a[start+x-1]*y[c-x];
   
    int sc=a[start+c-x-1]-a[start-1]*y[c-x];
 //   cout<<fs<<" "<<start+c-1<<" "<<start+x-1<<" "<<start+c-x-1<<" "<<sc<<endl;
    return (fs==sc);
}
signed main()
{
	//freopen("1.in","r",stdin);
	//freopen("a.out","w",stdout);
    cin>>n;
    cin>>s;
    init();
    cin>>q;
    while(q--)
    {
        memset(ys,0,sizeof(ys));
        //cout<<"p2"<<endl;
        int w,z;
        cin>>w>>z;
        int len=z-w+1,sz=0;
        int sl=len;
        for(int i=1;i<=cnt&&pri[i]*pri[i]<=sl;i++)
        {
            while(len%pri[i]==0)
            {
                ys[++sz]=pri[i];
                len/=pri[i];
            }
            if(len==1) break;
        }
        ys[0]=1;
        int ans=1;
        if(len!=1) ys[++sz]=len;
        for(int i=0;i<=sz;i++)
        {
            if(check(sl/ys[i],sl,w))
            {
                sl/=ys[i];
            }
          /*  else 
            {
            	ans*=ys[i];
            	break;
			}*/
		//	cout<<ys[i]<<" ";
        }
        cout<<sl<<endl;
    }
    return 0; 
}

求大佬帮助