#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int p = 131;
int len, ans, t, l, r, f[500010], a[500010], gx[500010],
 cnt, cx[500010];
char s[500010];
bool check(int l, int r, int s) {
	return a[r] - a[l + s - 1] * f[len - s] == 
	a[l + (len / s - 1) * s - 1] - a[l - 1] * f[len - s];
}
signed main () {
	int i, j, n;
	scanf("%u %s", &n, s + 1);
	f[0] = 1;
	for (i = 1; i <= n; ++i)
		a[i] = a[i - 1] * p + (int)(s[i]), f[i] = f[i - 1] * p;
	for (i = 2; i <= n; ++i) {
		if(!cx[i]) {
			gx[++cnt] = i;
			cx[i] = i;
		}
		for (j = 1; j <= cnt; ++j) {
			if(gx[j] > cx[i] || gx[j] * i > n) break;
			cx[gx[j] * i] = gx[j];
		}
	}
	int T;
	scanf("%u", &T);
	while(T--) {
		scanf("%u %u", &l, &r);
		len = ans = t = r - l + 1ull;
		while(t != 1) {
			int k = cx[t];
			while(t % k == 0 && check(l, r, ans / cx[t]))
				t /= k, ans /= k;
			while(t % k == 0) t /= k;
		}
		printf("%u\n", ans);
	}
}