#include<bits/stdc++.h>
using namespace std;
const int Mt=1e5;
inline char getc(){
	static char buf[Mt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	int r=0,f=1;char c=getc();
	while(!isdigit(c)){if(c=='-')f=-1;c=getc();}
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getc();
	return r*f;
}
int n;
string S;
int m;
const unsigned long long base=999983;
unsigned long long power[500005];
unsigned long long has[500005];
int gethas(int lt,int rt){
    return has[rt]-has[lt-1]*power[rt-lt+1];
}

int main(){
    cin>>n;
    cin>>S;
    S='?'+S;
    power[0]=1;
    for(int i=1;i<=n;i++){
        power[i]=power[i-1]*base;
    }
    for(int i=1;i<=n;i++){
        has[i]=has[i-1]*base+S[i];
    }
    m=read();
    while(m--){
        int lt,rt;
        lt=read();
        rt=read();
        int len=rt-lt+1;
        int ans=len;
        for(int p=1;p*p<=len;p++){
            if(len%p)continue;
            int q=len/p;
            // printf("%d %d %d %d\n",ans,p,q,len);
            if(gethas(lt,rt-p)==gethas(lt+p,rt)){
                ans=min(ans,p);
                break;
            }
            if(q==len)continue;
            if(gethas(lt,rt-q)==gethas(lt+q,rt)){
                ans=min(ans,q);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
重复后同S相等的最短的串
O(qsqrtn)，枚举循环节长度，对于每个长度的判断都是O(1)的。

8
aaabcabc
3
1 3
3 8
4 8
*/

RT,TLE on #3