#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long qpow(long long a, long long n) {
  long long r = 1 % P;
  for (a %= P; n; a = a * a % P, n >>= 1)
    if (n & 1) r = r * a % P;
  return r;
}
long long inv(long long first) {
  return first <= 1 ? 1 : inv(P % first) * (P - P / first) % P;
}
inline int rd() {
  int first = 0;
  char p = getchar();
  while (p < '0' || p > '9') p = getchar();
  while (p >= '0' && p <= '9') first = first * 10 + p - '0', p = getchar();
  return first;
}
const int N = 2e5 + 10;
int n, q, L[N], R[N], Log[N], a[N], L2[N];
int sum[N][26], trL[N << 2], trR[N << 2];
char s[N];
struct SA {
  int c[N], rk[N], h[N], sa[N], a[N], f[N][20];
  void build(int *a, int m) {
    a[n + 1] = rk[n + 1] = h[n + 1] = 0;
    int i, *first = rk, *second = h;
    for (i = 1; i <= m; i++) c[i] = 0;
    for (i = 1; i <= n; i++) c[first[i] = a[i]]++;
    for (i = 1; i <= m; i++) c[i] += c[i - 1];
    for (i = n; i; i--) sa[c[first[i]]--] = i;
    for (int k = 1, p; k <= n; k <<= 1) {
      p = 0;
      for (i = n - k + 1; i <= n; i++) second[++p] = i;
      for (i = 1; i <= n; i++)
        if (sa[i] > k) second[++p] = sa[i] - k;
      for (i = 1; i <= m; i++) c[i] = 0;
      for (i = 1; i <= n; i++) c[first[second[i]]]++;
      for (i = 1; i <= m; i++) c[i] += c[i - 1];
      for (i = n; i; i--) sa[c[first[second[i]]]--] = second[i];
      swap(first, second);
      first[sa[1]] = 1;
      p = 1;
      for (i = 2; i <= n; i++)
        first[sa[i]] = (second[sa[i - 1]] == second[sa[i]] &&
                        second[sa[i - 1] + k] == second[sa[i] + k])
                           ? p
                           : ++p;
      if (p == n) break;
      m = p;
    }
    for (i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j, k = 0; i <= n; i++) {
      if (k) k--;
      j = sa[rk[i] - 1];
      while (a[i + k] == a[j + k]) k++;
      h[rk[i]] = k;
    }
  }
  void init(int *a) {
    build(a, 100);
    for (int i = 1; i <= n; ++i) f[i][0] = h[i];
    for (int j = 1; j <= 19; ++j) {
      for (int i = 0; i + (1 << j - 1) - 1 <= n; ++i) {
        f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
      }
    }
  }
  int lcp(int l, int r) {
    if (l == r) return n - l + 1;
    l = rk[l], r = rk[r];
    if (l > r) swap(l, r);
    ++l;
    int t = Log[r - l + 1];
    return min(f[l][t], f[r - (1 << t) + 1][t]);
  }
} sa[2];
void add(int *tr, int o, int l, int r, int ql, int qr, int v) {
  if (tr[o] != INF) return;
  if (ql <= l && r <= qr) return tr[o] = v, void();
  if (((l + r) >> 1) >= ql) add(tr, (o << 1), l, ((l + r) >> 1), ql, qr, v);
  if (((l + r) >> 1) < qr)
    add(tr, ((o << 1) | 1), ((l + r) >> 1) + 1, r, ql, qr, v);
}
void dfs(int o, int l, int r) {
  if (l == r) {
    if (trL[o] <= n) L[l] = l - 2 * trL[o] + 1;
    if (trR[o] <= n) R[l] = l + 2 * trR[o] - 1;
    return;
  }
  trL[(o << 1)] = min(trL[(o << 1)], trL[o]),
            trL[((o << 1) | 1)] = min(trL[((o << 1) | 1)], trL[o]);
  trR[(o << 1)] = min(trR[(o << 1)], trR[o]),
            trR[((o << 1) | 1)] = min(trR[((o << 1) | 1)], trR[o]);
  dfs((o << 1), l, ((l + r) >> 1)), dfs(((o << 1) | 1), ((l + r) >> 1) + 1, r);
}
void build(int o, int l, int r) {
  trL[o] = trR[o] = INF;
  if (l != r)
    build((o << 1), l, ((l + r) >> 1)),
        build(((o << 1) | 1), ((l + r) >> 1) + 1, r);
}
void add(int l, int r, int v) {
  add(trR, 1, 1, n, l, r, v);
  add(trL, 1, 1, n, l + 2 * v - 1, r + 2 * v - 1, v);
}
int main() {
  scanf("%d%s%d", &n, s, &q);
  Log[0] = -1;
  for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = s[i - 1] - 'a' + 1;
    memcpy(sum[i], sum[i - 1], sizeof sum[0]);
    ++sum[i][s[i - 1] - 'a'];
  }
  sa[0].init(a);
  for (int i = 1; i <= n; ++i) a[i] = s[n - i] - 'a' + 1;
  sa[1].init(a);
  build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j + i <= n; j += i) {
      int p = sa[0].lcp(j, j + i);
      if (p >= 2 * i)
        add(j, j + i - 1, i);
      else if (p >= i)
        add(j, j + p - i, i);
      else {
        if (j + 2 * i - 1 > n) break;
        int s = sa[1].lcp(n - (j + i - 1) + 1, n - (j + 2 * i - 1) + 1);
        if (!s) continue;
        s = min(s, i - 1);
        int p2 = sa[0].lcp(j + i - s, j + 2 * i - s);
        if (p2 >= i) {
          int len = min(p2 - i + 1, s);
          add(j + i - s, j + i - s + len - 1, i);
        }
      }
    }
  for (int i = 1; i <= n; ++i) R[i] = INF;
  dfs(1, 1, n);
  for (int i = 1; i <= n; ++i) L2[i] = max(L2[i - 1], L[i]);
  int X = 2 * sqrt(n), Y = n / X;
  while (q--) {
    int l, r, ok = 0;
    scanf("%d%d", &l, &r);
    for (int i = 0; i <= 25; ++i)
      if (sum[r][i] - sum[l - 1][i] >= 2) ok = 1;
    if (!ok) {
      puts("-1");
      continue;
    }
    int len = r - l + 1;
    ok = 0;
    auto chk = [&](int first) {
      if (first == len) return false;
      int p = sa[0].lcp(l, l + first);
      return 1 + p / first >= len / first;
    };
    for (int i = 1; i * i <= len; ++i)
      if (len % i == 0) {
        if (chk(i) || chk(len / i)) {
          ok = 1;
          break;
        }
      }
    if (ok) {
      puts("1");
      continue;
    }
    auto chk2 = [&]() {
      int mx = min(X, len / 2);
      for (int i = 1; i <= mx; ++i) {
        int p = sa[0].lcp(l, r - i + 1);
        if (p >= i) return 1;
      }
      mx = min(n, sa[0].rk[l] + Y);
      for (int i = max(1, sa[0].rk[l] - Y); i <= mx; ++i) {
        int p = sa[0].sa[i], t = r - p + 1;
        if (l <= p && p <= r && t * 2 <= len && sa[0].lcp(l, p) >= t) return 1;
      }
      return 0;
    };
    if (R[l] <= r || L[r] >= l || chk2()) {
      puts("2");
      continue;
    }
    auto chk3 = [&](int first) {
      int p = s[first - 1] - 'a';
      return sum[r][p] - sum[l - 1][p] >= 2;
    };
    if (L2[r] >= l || chk3(l) || chk3(r))
      puts("3");
    else
      puts("4");
  }
}
