77分

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
using ULL = unsigned long long;
 
const int N = 500010;     // 数组大小
const int P = 131;        // 哈希的基数
 
int n, q, len, tot;
 
// 使用 vector 存储预处理数组，下标 1~n 使用
vector<ULL> h(N, 0), pwr(N, 0);   // h[i]：前 i 个字符的哈希； pwr[i] = P^i
vector<int> prime(N, 0), minp(N, 0); // 筛素数所用
string s;                         // 字符串 s（下标从1开始）
 
// 预处理：计算最小质因数以及哈希数组 pwr 和 h
void parse() {
    // 线性筛：计算 2~n 的最小质因数
    tot = 0;
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {   // i 为素数
            prime[++tot] = i;
            minp[i] = i;
        }
        for (int j = 1; j <= tot && prime[j] <= minp[i] && (long long)prime[j] * i <= n; j++) {
            minp[prime[j] * i] = prime[j];
        }
    }
    
    // 初始化哈希幂数组和前缀哈希数组
    pwr[0] = 1;
    for (int i = 1; i <= n; i++) {
        pwr[i] = pwr[i - 1] * P;
        // s[i] 为第 i 个字符（下标从1开始）
        h[i] = h[i - 1] * P + static_cast<ULL>(s[i]);
    }
}
 
// 计算子串哈希值：返回 s[l..r] 的哈希值（l、r 均从1开始）
ULL calc(int l, int r) {
    return h[r] - h[l - 1] * pwr[r - l + 1];
}
 
// 删除位置 x 对子串 s[l..r] 的贡献后得到的哈希值
// 即 s[l..x-1] 与 s[x+1..r] 拼接后的字符串哈希值
ULL del_calc(int l, int x, int r) {
    return calc(l, x - 1) * pwr[r - x] + calc(x + 1, r);
}
 
// 判断 s[a..b] 的子串（长度为 len）的循环节是否能缩短到长度 l（l 为候选周期长度）
// 这里 len 为全局变量，表示当前子串 s[a..b] 的长度
bool valid(int a, int b, int l) {
    // 根据候选循环节长度 l，设周期数为 (len / l) ，检查循环节是否重复
    // 这里采用原代码的计算方式：
    // 对于 s[a..b]，若删除一个位置后（具体位置依情况不同）拼接后哈希相等则说明满足条件
    ULL leftHash = 0, rightHash = 0;
    // 当删除的位置不同，其计算方式不同
    // 若候选位置为中间位置，则不删除任何字符，直接比较 s[a..x-1] 与 s[x+1..b]
    // 原代码中：
    //   如果 x == mid，则 l = calc(1, x-1) 和 r = calc(x+1, n)
    //   如果 x < mid，则 l = del_calc(1, x, mid) 和 r = calc(mid+1, n)
    //   如果 x > mid，则 l = calc(1, mid-1) 和 r = del_calc(mid, x, n)
    // 这里为了复用原思路，直接根据候选周期 l 判断：
    //    检查 s[a..b] 拆分为 (len / l) 个长度为 l 的块后是否所有块都相同
    // 注意：原代码中采用了删除某个位置后比较哈希值的方法，
    // 这里我们按照原代码写法，使用全局变量 len 表示子串长度
    int blocks = len / l; // 块数
    // 计算第1个块的哈希值
    ULL blockHash = calc(a, a + l - 1);
    // 遍历剩余块进行比较
    for (int i = 1; i < blocks; i++) {
        ULL curHash = calc(a + i * l, a + (i + 1) * l - 1);
        if (curHash != blockHash) return false;
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    // 读取字符串，注意题目中第二行包含 n 个小写字母，可能是连续输入
    string temp;
    cin >> temp;
    // 为了让下标从1开始，预先添加一个占位符
    s = " " + temp;
 
    cin >> q;
    parse();
 
    // 对每个询问，依次输出答案
    // 询问为 a, b（下标从1开始），要求求出子串 s[a..b] 的最短循环节长度
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        len = b - a + 1;
        int ans = len;
        int tmp = len;
 
        // 原算法思路：对 tmp 的质因数分解，逐步尝试缩短周期
        while (tmp != 1) {
            int t = minp[tmp]; // t 为 tmp 的最小质因数
            // 当候选答案 ans 能除以 t 时，尝试判断是否可以缩短周期
            while (tmp % t == 0 && ans % t == 0 && valid(a, b, ans / t)) {
                tmp /= t;
                ans /= t;
            }
            // 去除因子 t
            while (tmp % t == 0) {
                tmp /= t;
            }
        }
 
        cout << ans << "\n";
    }
    return 0;
}