#include <bits/stdc++.h>
using namespace std;
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  debug_out(H);
  cerr << " ";
  debug_out(T...);
}
template <typename T>
void debug_out(set<T> a) {
  vector<T> _a;
  for (T t : a) _a.push_back(t);
  debug_out(_a);
}
inline int inv(int a, int md) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}
class HASH {
 public:
  ;
  int a = 1e9 + 7;
  int b = 998244353;
  int x = 0, y = 0;
  HASH(){};
  HASH(int _x, int _y) : x(_x), y(_y) {
    if (x < 0) x += a;
    if (x >= a) x -= a;
    if (y < 0) y += b;
    if (y >= b) y -= b;
  };
  HASH operator+(const HASH &c) const { return HASH(x + c.x, y + c.y); }
  HASH operator-(const HASH &c) const { return HASH(x - c.x, y - c.y); }
  HASH operator*(const HASH &c) const {
    return HASH(((long long)x * c.x) % a, ((long long)y * c.y) % b);
  }
  HASH operator*(int c) const {
    return HASH(((long long)x * c) % a, ((long long)y * c) % b);
  }
  HASH operator/(const HASH &c) const {
    HASH _c = HASH(inv(c.x, a), inv(c.y, b));
    return *this * _c;
  }
  HASH operator/(int c) const { return *this / HASH(c, c); }
  bool operator<(const HASH &c) const {
    return make_pair(x, y) < make_pair(c.x, c.y);
  }
};
class suffix_hash {
 public:
  ;
  string s;
  vector<HASH> pref;
  HASH c;
  int n;
  vector<HASH> p;
  suffix_hash(string _s) : s(_s) {
    HASH c(97, 31);
    n = s.length();
    pref.resize(n + 1);
    p.resize(n + 1);
    p[0] = HASH(1, 1);
    for (int i = 1; i < n + 1; i++) {
      p[i] = p[i - 1] * c;
    }
    for (int i = 1; i < n + 1; i++) {
      pref[i] = pref[i - 1] + p[i] * (s[i - 1] - 'a' + 3);
    }
  }
  long long get(int l, int r) {
    int md = 1e9 + 7;
    HASH cc = (pref[r] - pref[l]) / p[l];
    return 1LL * cc.x * md + cc.y;
  }
};
template <typename T>
vector<int> build_lcp(int n, const T &s, const vector<int> &sa) {
  assert((int)sa.size() == n);
  vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[sa[i]] = i;
  }
  vector<int> lcp(max(n - 1, 0));
  int k = 0;
  for (int i = 0; i < n; i++) {
    k = max(k - 1, 0);
    if (pos[i] == n - 1) {
      k = 0;
    } else {
      int j = sa[pos[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
        k++;
      }
      lcp[pos[i]] = k;
    }
  }
  return lcp;
}
template <typename T>
vector<int> build_lcp(const T &s, const vector<int> &sa) {
  return build_lcp((int)s.size(), s, sa);
}
template <typename T>
vector<int> suffix_array(int n, const T &s, int char_bound) {
  vector<int> a(n);
  if (n == 0) {
    return a;
  }
  if (char_bound != -1) {
    vector<int> aux(char_bound, 0);
    for (int i = 0; i < n; i++) {
      aux[s[i]]++;
    }
    int sum = 0;
    for (int i = 0; i < char_bound; i++) {
      int add = aux[i];
      aux[i] = sum;
      sum += add;
    }
    for (int i = 0; i < n; i++) {
      a[aux[s[i]]++] = i;
    }
  } else {
    iota(a.begin(), a.end(), 0);
    sort(a.begin(), a.end(), [&s](int i, int j) { return s[i] < s[j]; });
  }
  vector<int> sorted_by_second(n);
  vector<int> ptr_group(n);
  vector<int> new_group(n);
  vector<int> group(n);
  group[a[0]] = 0;
  for (int i = 1; i < n; i++) {
    group[a[i]] = group[a[i - 1]] + (!(s[a[i]] == s[a[i - 1]]));
  }
  int cnt = group[a[n - 1]] + 1;
  int step = 1;
  while (cnt < n) {
    int at = 0;
    for (int i = n - step; i < n; i++) {
      sorted_by_second[at++] = i;
    }
    for (int i = 0; i < n; i++) {
      if (a[i] - step >= 0) {
        sorted_by_second[at++] = a[i] - step;
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      ptr_group[group[a[i]]] = i;
    }
    for (int i = 0; i < n; i++) {
      int x = sorted_by_second[i];
      a[ptr_group[group[x]]++] = x;
    }
    new_group[a[0]] = 0;
    for (int i = 1; i < n; i++) {
      if (group[a[i]] != group[a[i - 1]]) {
        new_group[a[i]] = new_group[a[i - 1]] + 1;
      } else {
        int pre = (a[i - 1] + step >= n ? -1 : group[a[i - 1] + step]);
        int cur = (a[i] + step >= n ? -1 : group[a[i] + step]);
        new_group[a[i]] = new_group[a[i - 1]] + (pre != cur);
      }
    }
    swap(group, new_group);
    cnt = group[a[n - 1]] + 1;
    step <<= 1;
  }
  return a;
}
template <typename T>
vector<int> suffix_array(const T &s, int char_bound) {
  return suffix_array((int)s.size(), s, char_bound);
}
template <typename T, class F = function<T(const T &, const T &)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;
  SparseTable(const vector<T> &a, const F &f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};
vector<int> get_dis(string a) {
  vector<int> sa = suffix_array(a, 256);
  vector<int> lcp = build_lcp(a, sa);
  int n = a.length();
  vector<vector<int>> rev(n);
  for (int i = 0; i < n - 1; i++) {
    rev[lcp[i]].push_back(i);
  }
  vector<vector<int>> where(n + 1);
  vector<deque<int>> segs(1);
  vector<set<int>> card(1);
  vector<int> to(n);
  for (int i = 0; i < n; i++) {
    segs[0].push_back(i);
    card[0].insert(sa[i]);
    if (sa[i] < n - 1) where[1].push_back(i);
  }
  auto Remove = [&](int pos) {
    int p = to[pos];
    int l = *segs[p].begin();
    int r = pos;
    if (r - l >= *prev(segs[p].end()) - pos - 1) {
      l = pos + 1;
      r = *prev(segs[p].end());
    }
    int cnt = segs.size();
    segs.resize(cnt + 1);
    card.resize(cnt + 1);
    for (int i = l; i <= r; i++) {
      card[p].erase(sa[i]);
      card[cnt].insert(sa[i]);
      to[i] = cnt;
    }
    int len = r - l + 1;
    while (len--) {
      if (r == pos) {
        segs[cnt].push_back(segs[p].front());
        segs[p].pop_front();
      } else {
        segs[cnt].push_front(segs[p].back());
        segs[p].pop_back();
      }
    }
  };
  vector<int> ret(n, n);
  for (int step = 1; step <= n; step++) {
    for (int i : rev[step - 1]) {
      Remove(i);
    }
    for (int i : where[step]) {
      int p = to[i];
      if (card[p].find(sa[i] + step) != card[p].end()) {
        ret[sa[i]] = step;
      } else {
        auto it = card[p].upper_bound(sa[i]);
        if (it != card[p].end()) {
          where[*it - sa[i]].push_back(i);
        }
      }
    }
  }
  return ret;
}
class suffix_tree {
 public:
  ;
  const int N = 26;
  struct edge {
    int L;
    int R;
    int from;
    int to;
    edge(){};
    edge(int _L, int _R, int _from, int _to)
        : L(_L), R(_R), from(_from), to(_to){};
  };
  struct state {
    int node;
    int go;
    state(){};
    state(int _node, int _go) : node(_node), go(_go){};
  };
  string a;
  int n;
  int cnt;
  vector<vector<int>> g;
  vector<edge> par;
  vector<int> suff;
  state cur = {0, 0};
  suffix_tree(string _a) : a(_a) {
    n = a.length();
    cnt = 1;
    g.resize(cnt, vector<int>(N, -1));
    par.emplace_back(-1, -1, -1, 0);
    suff.push_back(-1);
  }
  state split(state p) {
    int to = p.node;
    int dis = p.go;
    if (dis == 0) return p;
    int from = par[to].from;
    int L = par[to].L;
    int R = par[to].R;
    int s = R + 1 - dis;
    assert(L < s && s < R + 1);
    int id = a[L] - 'a';
    int sid = a[s] - 'a';
    cnt++;
    suff.push_back(-1);
    g.push_back(vector<int>(N, -1));
    g[from][id] = cnt - 1;
    g[cnt - 1][sid] = to;
    par.emplace_back(L, s - 1, from, cnt - 1);
    par[to] = edge(s, R, cnt - 1, to);
    return state(cnt - 1, 0);
  }
  state go(state p, int L, int R) {
    int len = 0;
    if (p.go) {
      if (p.go >= R - L + 1) {
        p.go -= R - L + 1;
        return p;
      } else {
        len += p.go;
        p.go = 0;
      }
    }
    int node = p.node;
    while (len < R - L + 1) {
      int id = a[L + len] - 'a';
      node = g[node][id];
      assert(~node);
      len += par[node].R - par[node].L + 1;
    }
    len -= R - L + 1;
    assert(0 <= len && len <= par[node].R - par[node].L);
    return state(node, len);
  }
  bool is_next(state p, int id) {
    int node = p.node;
    int R = par[node].R;
    if (p.go) {
      return (a[R - p.go + 1] - 'a') == id;
    }
    return g[node][id] != -1;
  }
  state suff_link(state p) {
    assert(p.node != 0);
    int node = p.node;
    if (suff[node] != -1) {
      node = suff[node];
      p = state(node, 0);
    } else {
      int from = par[node].from;
      int L = par[node].L;
      int R = par[node].R;
      node = suff[from];
      if (node == -1) {
        assert(from == 0);
        L++;
        node = 0;
      }
      p = state(node, 0);
      if (L <= R) {
        p = go(p, L, R);
      }
    }
    return p;
  }
  void add(int pos) {
    int id = a[pos] - 'a';
    vector<int> nodes;
    while (!is_next(cur, id)) {
      cur = split(cur);
      nodes.push_back(cur.node);
      if (cur.node == 0) break;
      cur = suff_link(cur);
    }
    for (int i = 0; i < (int)nodes.size() - 1; i++) {
      if (nodes[i] != 0) {
        suff[nodes[i]] = nodes[i + 1];
      }
    }
    if (nodes.size() && nodes.back() != 0) {
      suff[nodes.back()] = cur.node;
    }
    for (int node : nodes) {
      g[node][id] = cnt++;
      g.emplace_back(N, -1);
      par.emplace_back(pos, n - 1, node, cnt - 1);
      suff.push_back(-1);
    }
    assert(is_next(cur, id));
    if (nodes.empty() || nodes.back() != 0) cur = go(cur, pos, pos);
  }
  void build_tree() {
    for (int i = 0; i < n; i++) add(i);
  }
  vector<int> to_leaves() {
    cur = state(0, 0);
    cur = go(cur, 0, n - 1);
    vector<int> leaves;
    for (int iter = 0; iter <= n; iter++) {
      cur = split(cur);
      leaves.push_back(cur.node);
      if (iter < n) cur = suff_link(cur);
    }
    for (int i = 0; i < n; i++) {
      suff[leaves[i]] = leaves[i + 1];
    }
    return leaves;
  }
  vector<vector<int>> add_for_queries(vector<pair<int, int>> queries) {
    vector<int> S = to_leaves();
    int q = queries.size();
    vector<vector<int>> head(cnt);
    for (int i = 0; i < q; i++) {
      int l = queries[i].first;
      head[S[l]].push_back(i);
    }
    vector<state> que(q);
    vector<int> seq;
    vector<int> dep;
    function<void(int, int)> dfs = [&](int v, int d) {
      seq.push_back(v);
      dep.push_back(d);
      for (int id : head[v]) {
        int len = n - (1 + queries[id].second);
        int pos = lower_bound(dep.begin(), dep.end(), d - len) - dep.begin();
        int node = seq[pos];
        que[id] = state(node, dep[pos] - (d - len));
      }
      for (int i = 0; i < N; i++) {
        if (g[v][i] == -1) continue;
        int node = g[v][i];
        dfs(node, d + par[node].R - par[node].L + 1);
      }
      seq.pop_back();
      dep.pop_back();
    };
    dfs(0, 0);
    vector<vector<int>> ret(cnt);
    vector<int> id(q);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(),
         [&](int i, int j) { return que[i].go > que[j].go; });
    map<pair<int, int>, int> used;
    for (int i : id) {
      int v;
      if (used.count(make_pair(que[i].node, que[i].go)))
        v = used[make_pair(que[i].node, que[i].go)];
      else {
        v = split(que[i]).node;
        used[make_pair(que[i].node, que[i].go)] = v;
      }
      if ((int)ret.size() < cnt) ret.resize(cnt);
      ret[v].push_back(i);
    }
    return ret;
  }
};
void debug_out(suffix_tree::edge a) {
  cerr << "(" << a.from << " " << a.to << " " << a.L << " " << a.R << ")";
}
int n, q;
string s;
const int N = 26;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> s >> q;
  vector<pair<int, int>> query(q);
  for (int i = 0; i < q; i++) {
    cin >> query[i].first >> query[i].second;
    query[i].first--;
    query[i].second--;
  }
  suffix_hash Hasher(s);
  suffix_tree str(s);
  str.build_tree();
  vector<vector<int>> pos = str.add_for_queries(query);
  vector<int> leaves = str.to_leaves();
  int cnt = str.cnt;
  vector<int> head(cnt);
  for (int i : leaves) head[i] = 1;
  vector<set<int>> acquired(cnt);
  vector<set<pair<int, int>>> Left(cnt);
  vector<int> ret(q, 2);
  function<void(int, int)> dfs = [&](int v, int d) {
    vector<int> id;
    for (int i = 0; i < N; i++) {
      if (str.g[v][i] == -1) continue;
      int u = str.g[v][i];
      int len = str.par[u].R - str.par[u].L + 1;
      dfs(u, d + len);
      id.push_back(u);
    }
    if (v == 0) {
      for (int i : id) {
        for (auto j : Left[i]) {
          Left[v].insert(j);
        }
      }
      return;
    }
    sort(id.begin(), id.end(), [&](int i, int j) {
      return acquired[i].size() + Left[i].size() <
             acquired[j].size() + Left[j].size();
    });
    if (id.size()) {
      swap(acquired[v], acquired[id.back()]);
      swap(Left[v], Left[id.back()]);
      id.pop_back();
    }
    for (int i : id) {
      for (int dep : acquired[i]) {
        for (auto it = Left[v].lower_bound(make_pair(dep - d, -1));
             it != Left[v].end() && it->first < dep; it = Left[v].erase(it)) {
        };
        acquired[v].insert(dep);
      }
      for (auto add : Left[i]) {
        int len = add.first;
        auto it = acquired[v].upper_bound(len);
        if (it == acquired[v].end() || *it > len + d) {
          Left[v].insert(add);
        }
      }
    }
    if (head[v]) {
      int dep = d;
      for (auto it = Left[v].lower_bound(make_pair(dep - d, -1));
           it != Left[v].end() && it->first < dep; it = Left[v].erase(it)) {
      };
      acquired[v].insert(dep);
    }
    for (int i : pos[v]) {
      int len = n - 1 - (query[i].second);
      auto it = acquired[v].upper_bound(len);
      if (it == acquired[v].end() || *it >= len + d) {
        Left[v].insert(make_pair(len, i));
      }
    }
  };
  dfs(0, 0);
  for (auto i : Left[0]) ret[i.second] = -1;
  {
    vector<vector<int>> freq(n + 1, vector<int>(N));
    for (int i = 1; i <= n; i++) {
      freq[i] = freq[i - 1];
      freq[i][s[i - 1] - 'a']++;
    }
    vector<int> L = get_dis(s);
    L.push_back(n);
    reverse(s.begin(), s.end());
    vector<int> R = get_dis(s);
    R.push_back(n);
    reverse(s.begin(), s.end());
    reverse(R.begin(), R.end());
    vector<int> sL = L;
    for (int i = 0; i <= n; i++) {
      sL[i] = 2 * sL[i] + i;
    }
    SparseTable<int> d(sL, [&](int i, int j) { return min(i, j); });
    for (int i = 0; i < q; i++) {
      if (ret[i] != -1) continue;
      int l = query[i].first, r = query[i].second + 1;
      if (l + 2 * L[l] <= r || r - 2 * R[r] >= l) {
        ret[i] = 2;
      } else if (d.get(l, r) <= r) {
        ret[i] = 3;
      } else {
        int cl = s[l] - 'a';
        int cr = s[r - 1] - 'a';
        if (freq[r][cr] - freq[l][cr] > 1 || freq[r][cl] - freq[l][cl] > 1) {
          ret[i] = 3;
        } else {
          for (int j = 0; j < N; j++) {
            if (freq[r][j] - freq[l][j] > 1) {
              ret[i] = 4;
            }
          }
        }
      }
    }
  }
  vector<vector<int>> primes(n + 1);
  for (int i = 2; i <= n; i++) {
    if (primes[i].size()) continue;
    for (int j = i; j <= n; j += i) {
      primes[j].push_back(i);
    }
  }
  auto duplicate = [&](int l, int r, int d) {
    int len = r - l;
    HASH cc = (Hasher.pref[r] - Hasher.pref[l]) / Hasher.p[l];
    cc = cc * (Hasher.p[len * d] - HASH(1, 1)) / (Hasher.p[len] - HASH(1, 1));
    int md = 1e9 + 7;
    return 1LL * cc.x * md + cc.y;
  };
  auto check = [&](int l, int r) {
    int len = r - l;
    long long cc = Hasher.get(l, r);
    for (int i : primes[len]) {
      if (cc == duplicate(l, l + len / i, i)) return true;
    }
    return false;
  };
  for (int i = 0; i < q; i++) {
    int l = query[i].first, r = query[i].second + 1;
    if (check(l, r)) ret[i] = 1;
  }
  for (int i : ret) cout << i << "\n";
  return 0;
}
