#include<bits/stdc++.h>
#define ll long long
#define Maxn 500007
#define Mod 1000000007
#define Base 31
using namespace std ;
int tot , n , q , l , r , ans , len ;
char s[Maxn] ;
ll g[Maxn] , Prime[Maxn] , fra[Maxn] , hash[Maxn] ;
bool Isp[Maxn] ;
void GetPrime(int n)
{
	for(ll i = 2 ; i <= n ; i ++)
	{
		if(! Isp[i]) Prime[++ tot] = i , g[i] = i ;
		for(int j = 1 ; j <= tot && Prime[j] * i <= n ; j ++)
		{
			Isp[Prime[j] * i] = 1 , g[Prime[j] * i] = Prime[j] ;
			if(!(i % Prime[j])) break ;
		} 
	}
}
ll Sum(int x , int y)
{
	return ((hash[y] - hash[x - 1] * fra[y - x + 1]) % Mod + Mod) % Mod ;
}
void pre()
{
	fra[0] = 1 ;
	for(int i = 1 ; i <= n ; i ++)
		hash[i] = (hash[i - 1] * Base + s[i] - 'a' + 1) % Mod ,
		fra[i] = (fra[i - 1] * Base) % Mod ;
	
	
}
int main()
{
	cin >> n ;
	GetPrime(n) ;
	scanf("%s", s + 1) ;
	pre() ;
	//cout << Sum(4 , 7) << " " << Sum(5 , 8) << " " ;
	//cout << endl << endl ;
	cin >> q ;
	while(q --)
	{
		cin >> l >> r ;
		len = r - l + 1 ;
		ans = len ;
		//cout << len << "!" << endl ;
		if(Sum(l + 1 , r) == Sum(l , r - 1)) 
		{
			cout << "1" << endl ;
			continue ;
		}
		while(len > 1)
		{
			//cout << Sum(l + ans / g[len] , r) << " " << Sum(l , r - ans / g[len]) << endl ;
			if(Sum(l + ans / g[len] , r) == Sum(l , r - ans / g[len])) 
				ans /= g[len] ;
			len /= g[len] ;
			//cout << ans << " " << len ;
		}
		cout << ans << endl ;
	}
	return 0 ;
}