我真的是吐了…… 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,q,len,tot,prime[500010],minp[500010];
ull h[500010],p[500010];
char s[500010];
inline int read() {
    int x = 0,f = 1;
	char c = getchar();
    while(c < '0' || c > '9'){
	 	if(c == '-') f = -1;
		c = getchar();
	}
    while(c >= '0' && c <= '9'){
		x = (x << 1) + (x << 3) + c - '0';
		c = getchar();
	}
    return x * f;
}
inline void h_write(int x) {
    if(x < 0) putchar('-'),x = -x;
    if(x < 10) {
    	putchar(x + '0');
    	return;
	}
	h_write(x / 10),putchar(x % 10 + '0');
}
inline void write(int x){
	h_write(x),puts("");
}
void parse() {
    for(int i = 2; i <= n; i++) {
        if(!minp[i]) prime[++tot] = i,minp[i] = i;
        for(int j = 1; j <= tot; j++) {
            if(prime[j] > minp[i] || prime[j] * i > n) break;
            minp[prime[j] * i] = prime[j];
        }
    }
    p[0] = 1;
    for(int i = 1; i <= n; i++) h[i] = h[i - 1] * 131 + s[i],p[i] = p[i - 1] * 131;
}
bool valid(int a,int b,int l) {
    return h[b] - h[a + l - 1] * p[len - l] == h[a + (len / l - 1) * l - 1] - h[a - 1] * p[len - l];
}
int main() {
    n = read(),gets(s + 1),q = read();
    parse();
    while(q--) {
        int a,b,ans,t;
        a = read(),b = read();
        len = t = ans = b - a + 1;
        while(t - 1) {
            int t1 = minp[t];
            while(t % t1 == 0 && valid(a,b,ans / minp[t])) t /= t1,ans /= t1;
            while(t % t1 == 0) t /= t1;
        }
        write(ans);
    }
    return 0;
}
/*
Input:
8
aaabcabc
3
1 3
3 8
4 8
Output:
1
3
5
*/