#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>
#include <cstring>
#include <queue>
 
#define SZ(x) int(x.size())
#define hash Hsh
#define InTheNameOfGod ios::sync_with_stdio(false); cin.tie(0);
 
using namespace std;
 
const int N = 5 * 1000 * 100 + 121;
 
typedef long long ll;
 
vector <int> p[N];
ll pbase1[N], pbase2[N], phash1[N], phash2[N], n, q, base1 = 727, base2 = 701, mod = 1000*1000*1000+7;
string s;
 
void sieve () {
    for (int i = 2; i < N; i++)
        if (p[i].empty())
            for (int j = i; j < N; j += i)
                p[j].push_back(i);
}
 
void partial_hash (string &s)
{
    pbase1[0] = pbase2[0] = 1;
    for (int i = 1; i  <= s.size(); i++)
    {
        phash1[i] = (1ll * phash1[i-1] * base1 + s[i-1]) % mod;
        phash2[i] = (1ll * phash2[i-1] * base2 + s[i-1]) % mod;
        pbase1[i] = 1ll * pbase1[i-1] * base1 % mod;
        pbase2[i] = 1ll * pbase2[i-1] * base2 % mod;
    }
}
 
ll get_hash(int l, int r)
{
    ll hash1 = (phash1[r] - phash1[l] * pbase1[r-l] % mod + mod) % mod;
    ll hash2 = (phash2[r] - phash2[l] * pbase2[r-l] % mod + mod) % mod;
    return hash1 * mod + hash2;
}
 
bool good(int l, int r, int k) 
{
    return get_hash(l, r-k) == get_hash(l+k, r);
}
 
int main () 
{
    InTheNameOfGod;
    cin >> n >> s >> q;
    sieve();
    partial_hash(s);
    while (q--)
    {
        int l, r; cin >> l >> r; l--;
        int k = r-l;
        for (int i = 0; i < p[r-l].size(); i++)
        {
            int v = p[r-l][i];
            while (k % v == 0 && good(l, r, k / v)) 
                k /= v;
        }
        cout << k << "\n";
    }
}