Problem: Ildar took a band (a thin strip of cloth) and colored it. Formally, the band has n cells, each of them is colored into one of 26 colors, so we can denote each color with one of the lowercase letters of English alphabet. 

Ildar decided to take some segment of the band [l, r] (1 ≤ l ≤ r ≤ n) he likes and cut it from the band. So he will create a new band that can be represented as a string t = s_l s_{l+1} … s_r.

After that Ildar will play the following game: he cuts the band t into some new bands and counts the number of different bands among them. Formally, Ildar chooses 1 ≤ k ≤ |t| indexes 1 ≤ i_1 < i_2 < … < i_k = |t| and cuts t to k bands-strings t_1 t_2 … t_{i_1}, t_{i_1 + 1} … t_{i_2}, …, {t_{i_{k-1} + 1}} … t_{i_k} and counts the number of different bands among them. He wants to know the minimal possible number of different bands he can get under the constraint that at least one band repeats at least two times. The result of the game is this number. If it is impossible to cut t in such a way, the result of the game is -1.

Unfortunately Ildar hasn't yet decided which segment he likes, but he has q segments-candidates [l_1, r_1], [l_2, r_2], ..., [l_q, r_q]. Your task is to calculate the result of the game for each of them.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000) — the length of the band Ildar has.

The second line contains a string s consisting of n lowercase English letters — the band Ildar has.

The third line contains a single integer q (1 ≤ q ≤ 200 000) — the number of segments Ildar has chosen as candidates.

Each of the next q lines contains two integer integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) denoting the ends of the i-th segment.

Output

Output q lines, where the i-th of them should contain the result of the game on the segment [l_i, r_i].

Example

Input

9
abcabcdce
7
1 6
4 7
5 9
6 9
1 9
3 6
4 4


Output

1
-1
4
3
2
2
-1

Note

Consider the first example.

If Ildar chooses the segment [1, 6], he cuts a string t = abcabc. If he cuts t into two bands abc and abc, the band abc repeats two times and the number of different tapes is 1. So, the result of this game is 1.

If Ildar chooses the segment [4, 7], he cuts a string t = abcd. It is impossible to cut this band in such a way that there is at least one band repeating at least two times. So, the result of this game is -1.

If Ildar chooses the segment [3, 6], he cuts a string t = cabc. If he cuts t into three bands c, ab and c, the band c repeats two times and the number of different bands is 2. So, the result of this game is 2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
using namespace std;
const int maxn = 2e5 + 10;
const int logn = 19;
const int alf = 26;
int pw2[logn];
int lg2[maxn];
void make_sparse() {
  pw2[0] = 1;
  for (int i = 1; i < logn; i++) {
    pw2[i] = 2 * pw2[i - 1];
  }
  lg2[0] = -1;
  for (int i = 1; i < maxn; i++) {
    lg2[i] = lg2[i / 2] + 1;
  }
}
int table[maxn][logn];
int ns;
void sparse_min(vector<int> &v) {
  ns = v.size();
  for (int i = 0; i < ns; i++) {
    table[i][0] = v[i];
  }
  for (int c = 1; c < logn; c++) {
    for (int i = 0; i < ns; i++) {
      if (i + pw2[c - 1] < ns) {
        table[i][c] = min(table[i][c - 1], table[i + pw2[c - 1]][c - 1]);
      } else {
        table[i][c] = table[i][c - 1];
      }
    }
  }
}
int get_sp(int l, int r) {
  if (r <= l) return maxn;
  int lglr = lg2[r - l];
  return min(table[l][lglr], table[r - pw2[lglr]][lglr]);
}
struct cnt_tree {
  vector<pair<int, int>> tree;
  int n;
  cnt_tree() {}
  void make_cnt(pair<int, int> &v, char h) {
    v.first |= (1 << (h - 'a'));
    v.second = 0;
  }
  void sum_cnt(pair<int, int> &v, pair<int, int> l, pair<int, int> r) {
    v.first = l.first | r.first;
    v.second = (l.second | r.second | (l.first & r.first));
  }
  void build(const string &s, int v, int tl, int tr) {
    if (tl + 1 == tr) {
      make_cnt(tree[v], s[tl]);
      return;
    }
    int tm = (tl + tr) / 2;
    build(s, 2 * v + 1, tl, tm);
    build(s, 2 * v + 2, tm, tr);
    sum_cnt(tree[v], tree[2 * v + 1], tree[2 * v + 2]);
  }
  cnt_tree(const string &s) {
    n = s.size();
    tree.resize(4 * n);
    build(s, 0, 0, n);
  }
  void get(pair<int, int> &ans, int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return;
    if (tl >= l && tr <= r) {
      sum_cnt(ans, ans, tree[v]);
      return;
    }
    int tm = (tl + tr) / 2;
    get(ans, 2 * v + 1, tl, tm, l, r);
    get(ans, 2 * v + 2, tm, tr, l, r);
  }
  int get(int l, int r) {
    pair<int, int> ans;
    get(ans, 0, 0, n, l, r);
    return ans.second;
  }
};
struct min_tree {
  vector<int> tree;
  int n;
  min_tree() {}
  void build(vector<int> &a, int v, int tl, int tr) {
    if (tl + 1 == tr) {
      tree[v] = a[tl];
      return;
    }
    int tm = (tl + tr) / 2;
    build(a, 2 * v + 1, tl, tm);
    build(a, 2 * v + 2, tm, tr);
    tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
  }
  min_tree(vector<int> &a) {
    n = a.size();
    tree.resize(4 * n);
    build(a, 0, 0, n);
  }
  int get(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return maxn;
    if (tl >= l && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return min(get(2 * v + 1, tl, tm, l, r), get(2 * v + 2, tm, tr, l, r));
  }
  int get(int l, int r) { return get(0, 0, n, l, r); }
};
struct max_tree {
  vector<int> tree;
  int n;
  max_tree() {}
  void build(vector<int> &a, int v, int tl, int tr) {
    if (tl + 1 == tr) {
      tree[v] = a[tl];
      return;
    }
    int tm = (tl + tr) / 2;
    build(a, 2 * v + 1, tl, tm);
    build(a, 2 * v + 2, tm, tr);
    tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
  }
  max_tree(vector<int> &a) {
    n = a.size();
    tree.resize(4 * n);
    build(a, 0, 0, n);
  }
  int get(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return 0;
    if (tl >= l && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return max(get(2 * v + 1, tl, tm, l, r), get(2 * v + 2, tm, tr, l, r));
  }
  int get(int l, int r) { return get(0, 0, n, l, r); }
};
vector<int> suff(string &s) {
  s += '$';
  int n = s.size();
  vector<int> cnt(27);
  for (int i = 0; i < n - 1; i++) cnt[s[i] - 'a']++;
  vector<int> pos(27);
  pos[0] = 1;
  for (int i = 1; i < 27; i++) pos[i] = pos[i - 1] + cnt[i - 1];
  vector<int> a(n);
  for (int i = 0; i < n - 1; i++) a[pos[s[i] - 'a']++] = i;
  a[0] = n - 1;
  vector<int> c(n);
  int cc = 0;
  for (int i = 0; i < n - 1; i++) {
    c[a[i]] = cc;
    if (s[a[i]] != s[a[i + 1]]) cc++;
  }
  c[a[n - 1]] = cc;
  cnt.resize(n);
  pos.resize(n);
  for (int l = 1; l < n; l *= 2) {
    cnt.assign(n, 0);
    for (int i = 0; i < n; i++) cnt[c[i]]++;
    pos[0] = 0;
    for (int i = 1; i < n; i++) pos[i] = pos[i - 1] + cnt[i - 1];
    vector<int> na(n);
    for (int i = 0; i < n; i++) {
      int ind = (a[i] - l + n) % n;
      na[pos[c[ind]]++] = ind;
    }
    a = na;
    vector<int> nc(n);
    cc = 0;
    for (int i = 0; i < n - 1; i++) {
      nc[a[i]] = cc;
      if (c[a[i]] != c[a[i + 1]] || c[(a[i] + l) % n] != c[(a[i + 1] + l) % n])
        cc++;
    }
    nc[a[n - 1]] = cc;
    c = nc;
  }
  return a;
}
void relax(int &a, int b) { a = min(a, b); }
void relax_mx(int &a, int b) { a = max(a, b); }
vector<int> pos;
bool cmp(int a, int b) { return pos[a] < pos[b]; }
int n1;
string s1;
vector<int> suf;
vector<int> lcp;
int get_lcp(int a, int b) {
  a = pos[a];
  b = pos[b];
  if (a > b) swap(a, b);
  return get_sp(a + 1, b + 1);
}
vector<int> mst[4 * maxn];
vector<int> left_right[4 * maxn];
vector<int> right_left[4 * maxn];
max_tree spmx[4 * maxn];
void build(int v, int tl, int tr) {
  if (tl + 1 == tr) {
    mst[v] = {tl};
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v + 1, tl, tm);
  build(2 * v + 2, tm, tr);
  mst[v].resize(tr - tl);
  merge((mst[2 * v + 1]).begin(), (mst[2 * v + 1]).end(),
        (mst[2 * v + 2]).begin(), (mst[2 * v + 2]).end(), mst[v].begin(), cmp);
  spmx[v] = max_tree(mst[v]);
  vector<pair<int, int>> stack = {{0, -1}};
  left_right[v].resize(tr - tl);
  left_right[v][0] = -1;
  for (int i = 1; i < tr - tl; i++) {
    int lp = get_lcp(mst[v][i - 1], mst[v][i]);
    while (stack.size() > 1 && stack.back().second >= lp) {
      stack.pop_back();
    }
    left_right[v][i] = max(left_right[v][stack.back().first],
                           spmx[v].get(stack.back().first, i) + lp);
    stack.push_back({i, lp});
  }
  stack = {{tr - tl - 1, -1}};
  right_left[v].resize(tr - tl);
  right_left[v][tr - tl - 1] = -1;
  for (int i = tr - tl - 2; i >= 0; i--) {
    int lp = get_lcp(mst[v][i], mst[v][i + 1]);
    while (stack.size() > 1 && stack.back().second >= lp) {
      stack.pop_back();
    }
    right_left[v][i] = max(right_left[v][stack.back().first],
                           spmx[v].get(i + 1, stack.back().first + 1) + lp);
    stack.push_back({i, lp});
  }
}
void make_mst() { build(0, 0, n1); }
int get_inside(int v, int tl, int tr, int l, int r) {
  int p1 = upper_bound((mst[v]).begin(), (mst[v]).end(), l - 1, cmp) -
           mst[v].begin();
  int eqr;
  if (p1 == tr - tl) {
    eqr = 0;
  } else {
    eqr = get_lcp(l - 1, mst[v][p1]);
  }
  int bl = p1;
  int br = tr - tl;
  while (bl + 1 < br) {
    int bm = (bl + br) / 2;
    if (get_lcp(mst[v][bm], l - 1) >= eqr) {
      bl = bm;
    } else {
      br = bm;
    }
  }
  int eql;
  if (p1 == 0) {
    eql = 0;
  } else {
    eql = get_lcp(l - 1, mst[v][p1 - 1]);
  }
  int bl1 = p1;
  int br1 = -1;
  while (br1 + 1 < bl1) {
    int bm = (bl1 + br1 + 1) / 2;
    if (get_lcp(mst[v][bm], l - 1) >= eql) {
      bl1 = bm;
    } else {
      br1 = bm;
    }
  }
  int ans = -maxn;
  relax_mx(ans, spmx[v].get(bl1, p1) + eql);
  relax_mx(ans, spmx[v].get(p1, br) + eqr);
  if (bl1 >= 0) relax_mx(ans, left_right[v][bl1]);
  if (br != tr - tl) relax_mx(ans, right_left[v][bl]);
  if (ans >= r) return 1;
  return 0;
}
int get_prefix(int v, int tl, int tr, int l, int r) {
  if (tl >= r || tr <= l) return maxn;
  if (tl + 1 == tr) {
    if (get_lcp(l - 1, tl) + tl >= r) return tl;
    return maxn;
  }
  int tm = (tl + tr) / 2;
  if (tl >= l && tr <= r) {
    if (!get_inside(v, tl, tr, l, r)) {
      return maxn;
    }
    int g1 = get_prefix(2 * v + 1, tl, tm, l, r);
    if (g1 != maxn) return g1;
    return get_prefix(2 * v + 2, tm, tr, l, r);
  }
  int g1 = get_prefix(2 * v + 1, tl, tm, l, r);
  if (g1 != maxn) return g1;
  return get_prefix(2 * v + 2, tm, tr, l, r);
}
int get_prefix(int l, int r) {
  int g = get_prefix(0, 0, n1, l + 1, r);
  if (g == maxn) return 0;
  return r - g;
}
void all_about_one_string(string &s) {
  s1 = s;
  suf = suff(s1);
  n1 = s1.size();
  pos.resize(n1);
  for (int i = 0; i < n1; i++) {
    pos[suf[i]] = i;
  }
  lcp.resize(n1);
  int last = 0;
  for (int i = 0; i < n1 - 1; i++) {
    int j = pos[i];
    lcp[j] = last;
    for (int p = last;; p++) {
      if (s1[i + p] == s1[suf[j - 1] + p]) {
        lcp[j]++;
      } else {
        break;
      }
    }
    last = max(0, lcp[j] - 1);
  }
  sparse_min(lcp);
  make_mst();
}
int get(int l, int r) {
  int pr = get_prefix(l, r);
  if (pr != 0) {
    int k = r - l - pr;
    if ((r - l) % k == 0) {
      return 1;
    } else {
      return 2;
    }
  } else {
    return 5;
  }
}
void z(string &s, vector<int> &v) {
  int n = s.size();
  v.resize(n);
  int l = 0, r = 0;
  for (int i = 1; i < n; i++) {
    if (i >= r || v[i - l] + i >= r) {
      l = i;
      r = max(r, i);
      while (r < n && s[r] == s[r - l]) r++;
      v[i] = r - l;
    } else {
      v[i] = v[i - l];
    }
  }
}
vector<int> vv3;
vector<vector<int>> vv2;
void upd(int l, int r, int val) {
  if (l == r) {
    relax(vv3[l], val);
  }
  if (l <= r) {
    vv2[l].push_back(val);
    vv2[r + 1].push_back(-val);
  }
}
void make(string &s, int l, int r) {
  if (l + 1 == r) return;
  int m = (l + r) / 2;
  make(s, l, m), make(s, m, r);
  string sl;
  for (int i = m - 1; i >= l; i--) {
    sl += s[i];
  }
  for (int i = r - 1; i >= m; i--) {
    sl += s[i];
  }
  string sr;
  for (int i = m; i < r; i++) {
    sr += s[i];
  }
  for (int i = l; i < m; i++) {
    sr += s[i];
  }
  vector<int> vl;
  z(sl, vl);
  vector<int> vr;
  z(sr, vr);
  int n1 = m - l;
  int n2 = r - m;
  for (int i = m - 2; i >= l; i--) {
    int lz = vl[m - i - 1];
    lz = min(lz, i - l + 1);
    int rz = vr[n2 + i - l + 1];
    rz = min(rz, m - i - 2);
    int len = m - i - 1;
    upd(i - lz + 1, i - lz + 1 + lz + rz - len, len);
  }
  for (int i = m + 1; i < r; i++) {
    int rz = vr[i - m];
    rz = min(rz, r - i);
    int lz = vl[n1 + r - i];
    lz = min(lz, i - m);
    int len = i - m;
    upd(m - lz, m - lz + (lz + rz) - len, len);
  }
  for (int i = l; i < m; i++) {
    if (vr[n2 + i - l] >= m - i) {
      upd(i, i, m - i);
    }
  }
}
void z_plus(string &s, vector<int> &vec) {
  int n = s.size();
  vv2.assign(n + 1, vector<int>(0));
  vv3.assign(n, maxn);
  make(s, 0, n);
  vec = vv3;
  map<int, int> open;
  open.insert({maxn, 1});
  for (int i = 0; i < n; i++) {
    for (auto j : vv2[i]) {
      if (j > 0) {
        open[j]++;
      } else {
        open[-j]--;
        if (open[-j] == 0) {
          open.erase(-j);
        }
      }
    }
    relax(vec[i], (*(open.begin())).first);
  }
  for (int i = 0; i < n; i++) {
    vec[i] = i + 2 * vec[i];
  }
}
string s;
string rev_s;
int n;
cnt_tree cnt;
vector<int> v1, v2;
min_tree m1, m2;
void make() {
  make_sparse();
  cnt = cnt_tree(s);
  all_about_one_string(s);
  z_plus(s, v1);
  z_plus(rev_s, v2);
  m1 = min_tree(v1);
  m2 = min_tree(v2);
}
int full_get(int l, int r) {
  int cnt1 = cnt.get(l, r);
  int best = 5;
  if (cnt1) relax(best, 4);
  if (best == 5) return -1;
  if (cnt1 & (1 << (s[l] - 'a'))) relax(best, 3);
  if (cnt1 & (1 << (s[r - 1] - 'a'))) relax(best, 3);
  relax(best, get(l, r));
  if (best <= 2) return best;
  int pr;
  pr = m1.get(l, r);
  if (pr <= r) relax(best, 3);
  pr = m2.get(n - r, n - l);
  if (pr <= n - l) relax(best, 3);
  if (v1[l] <= r) relax(best, 2);
  if (v2[n - r] <= n - l) relax(best, 2);
  return best - 6 * (best == 5);
}
void input() {
  cin >> n;
  cin >> s;
  for (int i = n - 1; i >= 0; i--) {
    rev_s += s[i];
  }
}
void solve() {
  int q;
  cin >> q;
  int l, r;
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    l--;
    cout << full_get(l, r) << '\n';
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  input();
  make();
  solve();
  return 0;
}