#include<bits/stdc++.h>
#define ll long long
using namespace std ;

const int N = 1e6 + 0721 ;
const int base = 31 ;
const int mod = 123456791 ;
ll p[N] , ha[N] , ch[N] , minp[N] ;
char s[N] ;
bool vis[N] ;
int n , m , top ;

ll query( int l , int r ){
	if( l == 0 )
	return ha[r] ;
	else
	return ( ha[r] - ha[l-1] * ch[r-l+1] % mod + mod ) % mod ;
}

int main () {
	
	scanf("%d" ,&n ) ;
	scanf("%s" ,s ) ;
	n = strlen(s) ;
	
	ch[0] = 1 ;
	for( int i = 1 ; i < n ; ++i )
	ch[i] = ch[i-1] * base % mod ;
	
	ha[0] = s[0] - 'a' ;
	for( int i = 1 ; i < n ; ++i )
	ha[i] = ( ha[i-1] + ( s[i] - 'a' ) * ch[i] ) % mod ; 
	
	for( int i = 2 ; i <= n ; ++i ){
		if( !vis[i] )
		vis[i] = 1 , p[++top] = i ;
		for( int j = 1 ; j <= top && p[j] * i <= n ; ++j ){
			vis[i*p[j]] = 1 , minp[i*p[j]] = p[j] ;
			if( i % p[j] == 0 )
			break ;
		}
	}
	
	for( int i = 1 ; i <= top ; ++i )
	minp[p[i]] = p[i] ;
	
//	for( int i = 0 ; i <= n ; ++i )
//	cout<<i<<" "<<minp[i]<<endl ;
	
	scanf("%d" ,&m ) ;
	while(m--){
		int x , y ;
		scanf("%d%d" ,&x ,&y ) ;
		x-- , y-- ;
		ll len = y - x + 1 ;
		ll ans = len ;
		while( len > 1 ){
//			cout<<query( x + ans/minp[len] , y )<<" "<<query( x , y - ans/minp[len])<<endl ;
			if( query( x + ans/minp[len] , y ) == query( x , y - ans/minp[len] ) )
			ans= ans / minp[len] ;
			len= len / minp[len] ;
		
		}
			printf("%lld\n" ,ans ) ;
	}
	
	return 0 ;
}