#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 512345;
const unsigned long long HASHBASE = 131;
int n, q, l, r, len;
char c;
int a[MAXN];
unsigned long long R[MAXN];
unsigned long long hash[MAXN];
//返回 t 是否为 l ~ r 的一个循环节长度
//比较前 len - t 个和后 len - t 个是否一样
bool check(int l, int r, int t)
{
    unsigned long long h1 = hash[r - t] - hash[l - 1] * R[r - l + 1 - t];
    unsigned long long h2 = hash[r] - hash[l + t - 1] * R[r - l + 1 - t];
    return h1 == h2;
}
//线性筛
bool vis[MAXN];
int ptot, phi[MAXN], pri[MAXN];
int minP[MAXN]; //最小的质因子
void initP(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i])
            pri[++ptot] = i, minP[i] = i;
        for (int j = 1; j <= ptot && 1ll * i * pri[j] <= n; ++j)
        {
            vis[i * pri[j]] = 1;
            minP[i * pri[j]] = pri[j];
            if (!(i % pri[j]))
                break;
        }
    }
}
//当前的所有质因子
int nowPDtot;
int nowPD[MAXN];
int main()
{
    scanf("%d", &n);
    getchar();
    //线性筛
    initP(n);
    //预处理hash
    R[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%c", &c);
        //'a' ~ 'z' -> 0 ~ 25
        a[i] = c - 'a';
        //hash
        R[i] = R[i - 1] * HASHBASE;
        hash[i] = hash[i - 1] * HASHBASE + a[i];
    }
    //q 次询问
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &l, &r);
        //对长度分解质因子
        len = r - l + 1;
        for (nowPDtot = 0; len > 1; len /= minP[len])
            nowPD[++nowPDtot] = minP[len];
        //枚举所有质因子
        len = r - l + 1;
        for (int i = 1; i <= nowPDtot; i++)
        {
            if (check(l, r, len / nowPD[i]))
                len /= nowPD[i];
        }
        printf("%d\n", len);
    }
    return 0;
}