// https://szkopul.edu.pl/problemset/problem/h9erYqBkPcC8KtSvLhMzhgjw/site/?key=statement

// Okropny wiersz

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 500 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

int w[sizik], isNP[sizik];

void Sito() {
    for (int i = 2; i < sizik; i++) {
        if (!isNP[i]) {
            for (int j = 2 * i; j < sizik; j += i) {
                w[j] = i;
                isNP[j] = true;
            }
            w[i] = 1;
        }
    }
}

int hash_pref[sizik], powP[sizik];
constexpr int P = 37, mod = 1000 * 1000 * 1000 + 7;

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    for (int i = 1; i <= n; i++) {
        hash_pref[i] = (hash_pref[i - 1] + (int)(s[i - 1] - 'a') * powP[i - 1]) % mod;
    }

    int q;
    std::cin >> q;

    for (; q > 0; q--) {
        int l, r;
        std::cin >> l >> r;

        std::multiset<int> m1, m2;

        int ro = r - l + 1;
        int curr_l = ro;

        while (ro != 1) {
            if (w[ro] == 1) {
                m1.insert(ro);
                ro = 1;
            } else {
                m1.insert(w[ro]);
                ro /= w[ro];
            }
        }

        ro = curr_l;

        for (const auto& a : m1) {
            int tmp = curr_l / a;

            if (((powP[l + tmp - 1] * hash_pref[r - tmp] + powP[l - 1] * hash_pref[l + tmp - 1]) % mod) ==
                ((powP[l - 1] * hash_pref[r] + powP[l + tmp - 1] * hash_pref[l - 1]) % mod)) {
                curr_l = tmp;
            } else {
            }
        }

        std::cout << curr_l << '\n';
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    Sito();
    powP[0] = 1;
    for (int i = 1; i < sizik; i++) {
        powP[i] = (powP[i - 1] * P) % mod;
    }

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}