// Problem: P3538 [POI2012] OKR-A Horrible Poem
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3538
// Memory Limit: 125 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define int unsigned long long
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#define lowbit(x) ((x)&-(x))
#define abs(x) (((x)<(0))?(-(x)):(x))
#define swap(a,b) a^=b^=a^=b
#define INF 1e18
#define P 998244353
#define MAXN 2000005
using namespace std;
int n, pw[MAXN], pr[MAXN], minpri[MAXN], h[MAXN], q, l, r, mp[MAXN];
string s;
inline int hs(const int l, const int r)
{
	return h[r] - h[l - 1] * pw[r - l + 1];
}
inline bool check(const int k)
{
	// cout << "check(" << l << ", " << r << ", " << k << ") =" << (hs(l, r - k) == hs(l + k, r)) << endl;
	return hs(l, r - k) == hs(l + k, r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> s;
	s = " " + s;
	pw[0] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (pr[i] == 0)
		{
			for (int j = i; j <= n; j += i)
			{
				if (pr[j] == 0)
				{
					minpri[j] = i;
					pr[j] = 1;
				}
			}
		}
	}
	minpri[1] = 1;
	for (int i = 1; i <= n; i++)
	{
		pw[i] = pw[i - 1] * P;
		h[i] = h[i - 1] * P + s[i] - 'a' + 1;
	}
	// for (int i = 1; i <= n; i++)
	// {
		// cout << pr[i] << "\t";
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++)
	// {
		// cout << minpri[i] << "\t";
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++)
	// {
		// cout << pw[i] << "\t";
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++)
	// {
		// cout << h[i] << "\t";
	// }
	// cout << endl;
	cin >> q;
	// q = min(q, 1000000);
	while (q--)
	{
		cin >> l >> r;
		// for (int i = l; i <= r; i++)
		// {
			// cout << s[i];
		// }
		if (l == r)
		{
			cout << 1 << endl;
			continue;
		}
		int ans = 1;
		int x = r - l + 1;
		while (1)
		{
			if (mp[minpri[x]] == 0)
			{
				mp[minpri[x]] = minpri[x];
			}
			else
			{
				mp[minpri[x]] *= minpri[x];
			}
			if (check((r - l + 1) / mp[minpri[x]]) == 0)
			{
				int y = minpri[x];
				while (x % y == 0)
				{
					ans *= y;
					x /= y;
				}
				if (x == 1)
				{
					break;
				}
				continue;
			}
			if (x == 1)
			{
				break;
			}
			x /= minpri[x];
		}
		cout << ans << endl;
		x = r - l + 1;
		while (1)
		{
		    mp[minpri[x]] = 0;
		    x /= minpri[x];
		    if (x == 1)
		    {
		        break;
		    }
		}
	}
	return 0;
}