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>
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;
}