#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>
#include <cstring>
#include <queue>

#define SZ(x) int(x.size())
#define hash Hsh
#define InTheNameOfGod ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

const int N = 5 * 1000 * 100 + 121;

typedef long long ll;

vector <int> p[N];
ll pbase1[N], pbase2[N], phash1[N], phash2[N], n, q, base1 = 727, base2 = 701, mod = 1000*1000*1000+7;
string s;

void sieve () {
	for (int i = 2; i < N; i++)
		if (p[i].empty())
			for (int j = i; j < N; j += i)
				p[j].push_back(i);
}

void partial_hash (string &s)
{
	pbase1[0] = pbase2[0] = 1;
	for (int i = 1; i  <= s.size(); i++)
	{
		phash1[i] = (1ll * phash1[i-1] * base1 + s[i-1]) % mod;
		phash2[i] = (1ll * phash2[i-1] * base2 + s[i-1]) % mod;
		pbase1[i] = 1ll * pbase1[i-1] * base1 % mod;
		pbase2[i] = 1ll * pbase2[i-1] * base2 % mod;
	}
}

ll get_hash(int l, int r)
{
	ll hash1 = (phash1[r] - phash1[l] * pbase1[r-l] % mod + mod) % mod;
	ll hash2 = (phash2[r] - phash2[l] * pbase2[r-l] % mod + mod) % mod;
	return hash1 * mod + hash2;
}

bool good(int l, int r, int k) 
{
	return get_hash(l, r-k) == get_hash(l+k, r);
}

int main () 
{
	InTheNameOfGod;
	cin >> n >> s >> q;
	sieve();
	partial_hash(s);
	while (q--)
	{
		int l, r; cin >> l >> r; l--;
		int k = r-l;
		for (int i = 0; i < p[r-l].size(); i++)
		{
			int v = p[r-l][i];
			while (k % v == 0 && good(l, r, k / v)) 
				k /= v;
		}
		cout << k << "\n";
	}
}