#include <bits/stdc++.h>
using namespace std;
int read() {
  char c = getchar();
  int d = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; d = d * 10 + c - 48, c = getchar())
    ;
  return d * f;
}
const int M = 450;
const int N = 1 << 18;
const int inf = 1e9;
int n, m, s[N + 1], ans[N + 1];
struct qint {
  int x, y, id;
} q[N + 1];
vector<int> fc[N + 1];
void _input() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    s[i] = getchar();
    while (s[i] < 'a' || s[i] > 'z') s[i] = getchar();
    s[i] = s[i] - 'a' + 1;
  }
  m = read();
  for (int i = 1; i <= m; ++i) q[i].x = read(), q[i].y = read(), q[i].id = i;
}
class suffixarr {
 public:
  int n, s[N + 1], rk[N + 1], Rk[N + 1], he[N + 1], t1[N + 1], t2[N + 1],
      st[N + 1], H[N + 1][18];
  void _initrk() {
    memset(t1, 0, sizeof t1);
    for (int i = 1; i <= n; ++i) t1[s[i]]++;
    for (int i = 1; i <= N; ++i) t1[i] += t1[i - 1];
    for (int i = 1; i <= n; ++i) Rk[t1[s[i]]--] = i;
    for (int i = 1; i <= n; ++i)
      rk[Rk[i]] = rk[Rk[i - 1]] + (s[Rk[i]] != s[Rk[i - 1]]);
    for (int i = 1; i < n; i <<= 1) {
      memset(t1, 0, sizeof t1);
      for (int j = 1; j <= n; ++j) t1[rk[j + i]]++;
      for (int j = 1; j <= N; ++j) t1[j] += t1[j - 1];
      for (int j = 1; j <= n; ++j) t2[t1[rk[j + i]]--] = j;
      memset(t1, 0, sizeof t1);
      for (int j = 1; j <= n; ++j) t1[rk[j]]++;
      for (int j = 1; j <= N; ++j) t1[j] += t1[j - 1];
      for (int j = n; j >= 1; --j) Rk[t1[rk[t2[j]]]--] = t2[j];
      for (int j = 1; j <= n; ++j) {
        int x = Rk[j], y = Rk[j - 1];
        t1[x] = t1[y] + (rk[x] != rk[y] || rk[x + i] != rk[y + i]);
      }
      for (int j = 1; j <= n; ++j) rk[j] = t1[j];
      if (rk[n] == n) break;
    }
  }
  void _inithe() {
    for (int i = 1; i <= n; ++i) {
      int j = Rk[rk[i] - 1];
      int h = max(0, he[rk[i - 1]] - 1);
      while (s[i + h] == s[j + h]) h++;
      he[rk[i]] = h;
    }
  }
  void _initst() {
    for (int i = 1; i <= n; ++i) {
      st[i] = st[i - 1];
      if ((1 << st[i] + 1) <= i) st[i]++;
    }
    for (int i = 1; i <= n; ++i) {
      H[i][0] = he[i];
      for (int j = 1; j <= 17; ++j)
        if (i - (1 << j) + 1 >= 1)
          H[i][j] = min(H[i][j - 1], H[i - (1 << j - 1)][j - 1]);
    }
  }
  int _getlcp(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > n) return 0;
    if (x == y) return n - x + 1;
    x = rk[x];
    y = rk[y];
    if (x > y) swap(x, y);
    int t = st[y - x];
    x++;
    return min(H[x + (1 << t) - 1][t], H[y][t]);
  }
} s1, s2;
void _init1() {
  for (int i = 2; i <= n; ++i)
    if (((int)fc[i].size()) == 0)
      for (int j = 1; j <= n / i; ++j) fc[i * j].push_back(i);
  s1.n = n;
  for (int i = 1; i <= n; ++i) s1.s[i] = s[i];
  s1._initrk();
  s1._inithe();
  s1._initst();
  s2.n = n;
  for (int i = 1; i <= n; ++i) s2.s[n + 1 - i] = s[i];
  s2._initrk();
  s2._inithe();
  s2._initst();
}
void _work1() {
  for (int i = 1; i <= m; ++i) {
    int x = q[i].x, y = q[i].y, L = y - x + 1, o = q[i].id;
    for (int j = 0; j <= ((int)fc[L].size()) - 1; ++j) {
      int d = L / fc[L][j];
      if (s1._getlcp(x, x + d) >= L - d) {
        ans[o] = 1;
        break;
      }
    }
  }
}
struct node1 {
  int x, y, sa, sb;
} a1[N * 5];
int cs[N];
void pushdown1(int t) {
  if (a1[t].sa != inf) {
    a1[t << 1].sa = a1[t << 1 | 1].sa = a1[t].sa;
    a1[t].sa = inf;
  }
  if (a1[t].sb != inf) {
    a1[t << 1].sb = a1[t << 1 | 1].sb = a1[t].sb;
    a1[t].sb = inf;
  }
}
void build1(int t, int x, int y) {
  a1[t].x = x;
  a1[t].y = y;
  a1[t].sa = a1[t].sb = inf;
  if (x == y) return;
  int m = (x + y) >> 1;
  build1(t << 1, x, m);
  build1(t << 1 | 1, m + 1, y);
}
void update1(int t, int x, int y, int s, int tp) {
  if (x <= a1[t].x && a1[t].y <= y) {
    if (tp == 1) a1[t].sa = s;
    if (tp == 2) a1[t].sb = s;
    return;
  }
  pushdown1(t);
  int m = (a1[t].x + a1[t].y) >> 1;
  if (x <= m) update1(t << 1, x, y, s, tp);
  if (y > m) update1(t << 1 | 1, x, y, s, tp);
}
int ask1(int t, int x, int y, int tp) {
  assert(tp == 1 || tp == 2);
  if (x <= a1[t].x && a1[t].y <= y) {
    if (tp == 1) return a1[t].sa;
    if (tp == 2) return a1[t].sb;
  }
  int m = (a1[t].x + a1[t].y) >> 1;
  if (tp == 1) {
    int res = -inf;
    if (x <= m) res = max(res, ask1(t << 1, x, y, tp));
    if (y > m) res = max(res, ask1(t << 1 | 1, x, y, tp));
    return res;
  }
  if (tp == 2) {
    int res = inf;
    if (x <= m) res = min(res, ask1(t << 1, x, y, tp));
    if (y > m) res = min(res, ask1(t << 1 | 1, x, y, tp));
    return res;
  }
}
void scan1(int t, int x, int y) {
  if (x == y) {
    a1[t].sa = x - a1[t].sa + 1;
    a1[t].sb = x + a1[t].sb - 1;
    return;
  }
  int m = (x + y) >> 1;
  pushdown1(t);
  scan1(t << 1, x, m);
  scan1(t << 1 | 1, m + 1, y);
  a1[t].sa = max(a1[t << 1].sa, a1[t << 1 | 1].sa);
  a1[t].sb = min(a1[t << 1].sb, a1[t << 1 | 1].sb);
}
void _init2() {
  build1(1, 1, n);
  for (int i = n; i >= 1; --i)
    for (int j = 1; j + i <= n; j += i) {
      int J = j + i;
      int L1 = min(i - 1, s2._getlcp(n + 1 - (j - 1), n + 1 - (J - 1)));
      int L2 = min(i, s1._getlcp(j, J));
      int x = J - L1 + i - 1, y = J + L2 - 1;
      if (x <= y) {
        update1(1, x, y, i * 2, 1);
        update1(1, x - 2 * i + 1, y - 2 * i + 1, i * 2, 2);
      }
    }
  scan1(1, 1, n);
}
void _work2() {
  for (int i = 1; i <= m; ++i) {
    int x = q[i].x, y = q[i].y, o = q[i].id;
    if (ans[o]) continue;
    if (ask1(1, y, y, 1) >= x)
      ans[o] = 2;
    else if (ask1(1, x, x, 2) <= y)
      ans[o] = 2;
    else {
      for (int j = max(x + 1, y - M); j <= y; ++j)
        if (j + s1._getlcp(x, j) - 1 >= y) {
          ans[o] = 2;
          break;
        }
      if (ans[o] != 2) {
        int p = s1.rk[x];
        for (int j = max(1, p - M); j <= min(n, p + M); ++j) {
          int q = s1.Rk[j];
          if (q > x && q <= y && q + s1._getlcp(x, q) - 1 >= y) {
            ans[o] = 2;
            break;
          }
        }
      }
    }
  }
}
int ct[27][N];
void _init3() {
  for (int i = 1; i <= n; ++i) ct[s[i]][i] = 1;
  for (int i = 1; i <= 26; ++i)
    for (int j = 1; j <= n; ++j) ct[i][j] += ct[i][j - 1];
}
void _work3() {
  for (int i = 1; i <= m; ++i) {
    int x = q[i].x, y = q[i].y, o = q[i].id;
    if (ans[o]) continue;
    if (ct[s[x]][y] - ct[s[x]][x] > 0)
      ans[o] = 3;
    else if (ct[s[y]][y - 1] - ct[s[y]][x - 1] > 0)
      ans[o] = 3;
    else if (ask1(1, x, y, 1) >= x)
      ans[o] = 3;
  }
}
void _work4() {
  for (int i = 1; i <= m; ++i) {
    int x = q[i].x, y = q[i].y, o = q[i].id;
    if (ans[o]) continue;
    for (int j = 1; j <= 26; ++j)
      if (ct[j][y] - ct[j][x - 1] > 1) {
        ans[o] = 4;
        break;
      }
  }
}
int main() {
  _input();
  _init1();
  _work1();
  _init2();
  _work2();
  _init3();
  _work3();
  _work4();
  for (int i = 1; i <= m; ++i)
    if (ans[i] == 0) ans[i] = -1;
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}
