对于长度为 $len$ 的字符串。如果最小循环节长度为 $x$，那么 $kx$ 也是循环节。且 $len$ 必然也可以写成 $kx$ 的形式

对于一个长度为 $12$ 的字符串，如果最小循环节长度是 $x=2$。

初始的长度 $12 = 6x$，我们就可以依次试除 $12$ 的质因子（$2,2,3$）来把 $k=6$ 除掉：

• 试除 $2$：$\frac{12}{2} = 6$：$6$是循环节，接下来考虑 $6$ 的循环节即可。
• 试除 $2$：$\frac{6}{2} = 3$：$3$不是循环节，接下来继续考虑 $6$ 的循环节。
• 试除 $3$：$\frac{6}{3} = 2$：$2$是循环节，接下来考虑 $2$ 的循环节即可。

试除结束，最小循环节长度为 $2$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
bool vis[MAXN + 5];
int ptot, minP[MAXN + 5], pri[MAXN + 5];
void initP()
{
    minP[1] = 1;
    for (int i = 2; i < MAXN; ++i)
    {
        if (!vis[i])
            minP[i] = i, pri[ptot++] = i;
        for (int j = 0; j < ptot; ++j)
        {
            if (1ll * i * pri[j] >= MAXN)
                break;
            vis[i * pri[j]] = 1;
            minP[i * pri[j]] = pri[j];
            if (i % pri[j] == 0)
                break;
        }
    }
}
string s;
// Hash
const long long MOD = 1000000007;
const int P = 29;
long long myHash[MAXN + 5];
long long powP[MAXN + 5];
// 初始化 s[1]~s[n] 的哈希
void initHash(int n)
{
    powP[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        myHash[i] = (myHash[i - 1] * P + s[i] - 'a' + 1) % MOD;
        powP[i] = powP[i - 1] * P % MOD;
    }
    powP[n + 1] = powP[n] * P % MOD;
}
// 获取 s[l]~s[r] 的哈希值
int getHash(int l, int r)
{
    return (myHash[r] - myHash[l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
}
// 存质因数
int PD[MAXN + 5], PDtot;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    initP();
    int n, q;
    cin >> n;
    cin >> s;
    s = "^" + s + "$";
    initHash(n);
    cin >> q;
    while (q--)
    {
        int l, r, len;
        cin >> l >> r;
        len = r - l + 1;
        if (len == 1 || getHash(l, r - 1) == getHash(l + 1, r))
        {
            cout << "1\n";
            continue;
        }
        // 给len质因数分解
        PDtot = 0;
        for (int i = len; i > 1; i /= minP[i])
            PD[++PDtot] = minP[i];
        // 找最小循环节
        for (int i = 1; i <= PDtot; i++)
        {
            int now = len / PD[i];
            if (getHash(l + now, r) == getHash(l, r - now))
                len /= PD[i];
        }
        cout << len << "\n";
    }
    return 0;
}