#include <bits/stdc++.h>
const int maxn = 400010, maxq = 400010;
int n, cnt[maxn], tmp[maxn], lg[maxn];
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
struct SA {
  char S[maxn];
  int nxt[maxn], mn[maxn], sa[maxn], r[2][maxn], *rk, ht[20][maxn];
  void make() {
    for (int i = 0; i < 128; i++) cnt[i] = 0, tmp[i] = 1 << 30;
    mn[n] = 1 << 30;
    for (int i = n; i--;)
      nxt[i] = tmp[S[i]], tmp[S[i]] = i, mn[i] = min(nxt[i], mn[i + 1]);
    for (int i = 0; i < n; i++) cnt[S[i]]++;
    for (int i = 1; i < 128; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i--;) sa[--cnt[S[i]]] = i;
    int tot = 0;
    rk = *r;
    for (int i = 0; i < n; i++)
      rk[sa[i]] = i && S[sa[i - 1]] == S[sa[i]] ? tot - 1 : tot++;
    for (int k = 1, *t = r[1]; tot < n; k *= 2) {
      for (int i = 0; i < k; i++) tmp[i] = i + n - k;
      for (int i = 0, j = k; i < n; i++)
        if (sa[i] >= k) tmp[j++] = sa[i] - k;
      for (int i = 0; i < tot; i++) cnt[i] = 0;
      for (int i = 0; i < n; i++) cnt[rk[i]]++;
      for (int i = 1; i < tot; i++) cnt[i] += cnt[i - 1];
      for (int i = n; i--;) sa[--cnt[rk[tmp[i]]]] = tmp[i];
      rk[n] = -1;
      for (int i = tot = 0; i < n; i++)
        t[sa[i]] = i && rk[sa[i - 1]] == rk[sa[i]] &&
                           rk[sa[i - 1] + k] == rk[sa[i] + k]
                       ? tot - 1
                       : tot++;
      std::swap(rk, t);
    }
    for (int i = 0, h = 0; i < n; ht[0][rk[i++]] = h)
      for (h ? --h : 0; rk[i] + 1 < n && S[i + h] == S[sa[rk[i] + 1] + h]; h++)
        ;
    for (int k = 1; k <= lg[n]; k++)
      for (int i = 0; i + (1 << k) <= n; i++)
        ht[k][i] = min(ht[k - 1][i], ht[k - 1][i + (1 << k - 1)]);
  }
  int lcp(int i, int j) {
    if (i == n || j == n) return 0;
    int k;
    if ((i = rk[i]) > (j = rk[j]))
      return k = lg[i - j], min(ht[k][j], ht[k][i - (1 << k)]);
    return k = lg[j - i], min(ht[k][i], ht[k][j - (1 << k)]);
  }
} S0, S1;
int R[maxq], ans[maxq];
std::vector<int> pf[maxn], qs[maxn];
int ul[maxn], ur[maxn], dl[maxn], dr[maxn], ml[maxn], pl[maxn], pr[maxn],
    list[maxn];
int find(int* u, int i) { return u[i] == i ? i : u[i] = find(u, u[i]); }
void upd(int* u, int* d, int l, int r, int x) {
  while ((l = find(u, l)) < r) d ? d[l] = x : 0, u[l] = find(u, l + 1);
}
int calc(int l, int r, int br) {
  int len = r - l;
  for (int i = pf[len].size(); i--;) {
    int p = len / pf[len][i];
    if (S0.lcp(l, l + p) >= len - p) return 1;
  }
  if (dl[l] && l + dl[l] * 2 <= r) return 2;
  if (dr[r] && r - dr[r] * 2 >= l) return 2;
  if (r > br && ul[r] > r) return 2;
  for (int i = 1; l + i < r && l + i <= br; i++)
    if (S0.lcp(l, r - i) >= i) return 2;
  if (S0.nxt[l] < r || S1.nxt[n - r] < n - l || ml[l] <= r) return 3;
  if (S0.mn[l] < r) return 4;
  return -1;
}
int main() {
  scanf("%d%s", &n, S0.S);
  for (int i = n, j = 0; i--; j++) S1.S[j] = S0.S[i];
  for (int i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
    if (!pf[i].size())
      for (int j = i; j <= n; j += i) pf[j].push_back(i);
  }
  S0.make();
  S1.make();
  for (int i = 0; i <= n + 1; i++) ul[i] = ur[i] = i;
  for (int l = 1; l <= n / 2; l++) {
    int la = -1;
    for (int i = 0; i + l <= n; i += l)
      if (i > la) {
        int pl = i - S1.lcp(n - i - l, n - i), pr = i + S0.lcp(i, i + l);
        if (pr - pl >= l) {
          upd(ul, dl, pl, pr - l + 1, l);
          upd(ur, dr, pl + l * 2, pr + l + 1, l);
        }
        la = pr;
      }
  }
  ml[n] = 1 << 30;
  for (int i = n; i--;) {
    ml[i] = ml[i + 1];
    if (dl[i]) ml[i] = min(ml[i], i + dl[i] * 2);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0, l; i < q; i++) {
    scanf("%d%d", &l, R + i);
    qs[l - 1].push_back(i);
  }
  int b = 0;
  while (b * b < n * 4) b++;
  for (int bl = 0, br = b; bl < n; bl = br, br += b) {
    if (br > n) br = n;
    for (int i = 0; i <= br; i++) cnt[i] = 0;
    for (int i = br + 1; i <= n; i++) {
      ul[i] = i;
      pl[i] = br - S1.lcp(n - i, n - br);
      cnt[pl[i]]++;
    }
    for (int i = 0; i < br; i++) cnt[i + 1] += cnt[i];
    int tot = cnt[br];
    for (int i = n; i > br; i--) tmp[--cnt[pl[i]]] = i;
    for (int l = bl, i = 0; l < n && l < br; l++) {
      for (; i < tot && pl[tmp[i]] <= l; i++)
        upd(ul, 0, tmp[i], tmp[i] + S0.lcp(br, tmp[i]) + 1, 0);
      for (int id = qs[l].size(); id--;) {
        int x = qs[l][id];
        ans[x] = calc(l, R[x], br);
      }
    }
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
