#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define p 1000007
#define ull unsigned long long
using namespace std;
ull hsh[500005], _pow[500005], n;
void get_hsh(ull ha[], string s){for(int i = 1 ; i <= s.length() ; i++) ha[i] = ha[i-1]*p+s[i-1];}
void get_pow(ull pw[]) {pw[0] = 1;for(int i = 1 ; i <= n ; i++) pw[i] = pw[i-1]*p;}
ull _hash(ull ha[], int l, int r) {return ha[r] - ha[l-1]*_pow[r-l+1];}
bool vis[500005]; int prime[500005], tot;
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	string str; cin >> str;
	get_hsh(hsh, str); get_pow(_pow); 
	for(int i = 2 ; i <= n ; i++) {
		if(!vis[i]){
			prime[++tot] = i;
			for(int j = i ; j <= n/i ; j++) vis[i*j] = 1;
		}
	}
	int q;
	cin >> q;
	while(q--){
		int l, r; cin >> l >> r;
		int len = r-l+1; int ans = 2e9;
		for(int i = 1 ; i <= tot ; i++){
			while(len % prime[i] == 0){	
				ull h1 = _hash(hsh, l, r-len), h2 = _hash(hsh, l+len, r);
				if(h1 == h2) ans = min(ans, len);
				len /= prime[i];
			}
			if(len == 1) {
				ull h1 = _hash(hsh, l, r-len), h2 = _hash(hsh, l+len, r);
				if(h1 == h2) ans = min(ans, len);
				break;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

AC1 WA7 TLE2 不排除rz错误 过了样例