#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int base = 13331;

vector< pair<int, int> > prime[500001];
long long hash[500001], power[500001];
bool check[500001];
char str[500001];

int main() {
	int n, q;
	scanf("%d%s%d", &n, str, &q);
	memset(check, false, sizeof(check));
	for (int i = 2; i <= n; i ++)
		if (! check[i])
			for (int j = i; j <= n; j += i) {
				int tmp = j, cnt = 0;
				while (tmp % i == 0) {
					cnt ++;
					tmp /= i;
				}
				prime[j].push_back(make_pair(i, cnt));
				check[j] = true;
			}
	hash[0] = 0;
	for (int i = 0; i < n; i ++)
		hash[i+1] = hash[i] * base + str[i];
	power[0] = 1;
	for (int i = 1; i < n; i ++)
		power[i] = power[i-1] * base;
	for (int i = 0; i < q; i ++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a --;
		int len = b - a, res = 1;
		for (int j = 0; j < prime[len].size(); j ++) {
			int p = prime[len][j].first, cnt = prime[len][j].second, now = 1;
			for (int k = 0; k < cnt; k ++) now *= p;
			for (int k = cnt; k > 0; k --) {
				int l = len / now;
				long long t1 = hash[b-l] - hash[a] * power[b-a-l];
				long long t2 = hash[b] - hash[a+l] * power[b-a-l];
				if (t1 == t2) {
					res *= now;
					break;
				}
				now /= p;
			}
		}
		printf("%d\n", len / res);
	}
	
	return 0;
}