#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], rk[N], rk2[N], h[N], sa[N];
int sum[N][26], trL[N << 2], trR[N << 2];
char s[N];
const int Max_N = N;
namespace SA_IS {
int *sa;
template <typename _Char>
void push_S(const _Char s[], const int first, int cur[]) {
  sa[--cur[static_cast<int>(s[first])]] = first;
};
template <typename _Char>
void push_L(const _Char s[], const int first, int cur[]) {
  sa[cur[static_cast<int>(s[first])]++] = first;
};
template <typename _Char>
void induced_sort(const int v[], const int n, const int m, const _Char s[],
                  char type[], int cnt[], int n1) {
  std::fill(sa, sa + n, 0);
  int *cur = cnt + m;
  std::copy(cnt, cnt + m, cur);
  for (int i = n1 - 1; i >= 0; --i) push_S(s, v[i], cur);
  std::copy(cnt, cnt + m - 1, cur + 1);
  for (int i = 0; i < n; ++i)
    if (sa[i] > 0 && type[sa[i] - 1] == 0) push_L(s, sa[i] - 1, cur);
  std::copy(cnt, cnt + m, cur);
  for (int i = n - 1; i >= 0; --i)
    if (sa[i] > 0 && type[sa[i] - 1]) push_S(s, sa[i] - 1, cur);
}
template <typename _Char>
bool lms_equal(const _Char s[], char type[], int first, int second) {
  if (s[first] == s[second])
    while (s[++first] == s[++second] && type[first] == type[second])
      if (type[first] == 2 || type[second] == 2) return true;
  return false;
}
char *tp;
bool cmp(const int first) { return tp[first] != 2; }
template <typename _Char>
void sais_core(const int n, const int m, const _Char s[], char type[],
               int lms[], int cnt[]) {
  int n1 = 0, ch = -1;
  tp = type;
  type[n - 1] = 1;
  for (int i = n - 2; i >= 0; --i)
    type[i] = s[i] == s[i + 1] ? type[i + 1] : s[i] < s[i + 1];
  std::fill(cnt, cnt + m, 0);
  for (int i = 0; i < n; ++i) ++cnt[static_cast<int>(s[i])];
  std::partial_sum(cnt, cnt + m, cnt);
  for (int i = 1; i < n; ++i)
    if (type[i - 1] == 0 && type[i] == 1) type[i] = 2, lms[n1++] = i;
  induced_sort(lms, n, m, s, type, cnt, n1);
  int *s1 = std::remove_if(sa, sa + n, cmp);
  for (int i = 0; i < n1; ++i)
    s1[sa[i] >> 1] = ch += ch <= 0 || !lms_equal(s, type, sa[i], sa[i - 1]);
  for (int i = 0; i < n1; ++i) s1[i] = s1[lms[i] >> 1];
  if (ch + 1 < n1)
    sais_core(n1, ch + 1, s1, type + n, lms + n1, cnt + m);
  else
    for (int i = 0; i < n1; ++i) sa[s1[i]] = i;
  for (int i = 0; i < n1; ++i) lms[n1 + i] = lms[sa[i]];
  induced_sort(lms + n1, n, m, s, type, cnt, n1);
}
template <typename _Char>
void main(const _Char s[], const int n, const int m) {
  static int _lms[Max_N], _cnt[Max_N << 1];
  static char _type[Max_N << 1];
  sais_core(n + 1, m, s, _type, _lms, _cnt);
}
}  // namespace SA_IS
void calc(int *s, int *rk, int n) {
  for (int i = 1; i <= n; ++i) ++sa[i];
  for (int i = 1; i <= n; i++) rk[sa[i]] = i;
  for (int i = 1, j, k = 0; i <= n; i++) {
    if (rk[i] == 1) continue;
    if (k) k--;
    j = sa[rk[i] - 1];
    while (s[i + k] == s[j + k]) k++;
    h[rk[i]] = k;
  }
}
void build(int *a, int *rk, int n) {
  SA_IS::sa = sa;
  a[n + 1] = 0;
  SA_IS::main(a + 1, n, 128);
  calc(a, rk, n);
}
int f[20][N], g[20][N];
void init(int a[N], int f[20][N], int n) {
  Log[0] = -1;
  for (int i = 1; i <= n; ++i) f[0][i] = a[i], Log[i] = Log[i >> 1] + 1;
  for (int j = 1; j <= 19; ++j)
    for (int i = 0; i + (1 << j - 1) - 1 <= n; ++i) {
      f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
    }
}
int RMQ(int f[20][N], int l, int r) {
  int t = Log[r - l + 1];
  return min(f[t][l], f[t][r - (1 << t) + 1]);
}
int lcp(int first, int second) {
  first = rk[first], second = rk[second];
  if (first > second) swap(first, second);
  return RMQ(f, first + 1, second);
}
int lcs(int first, int second) {
  first = rk2[n - first + 1], second = rk2[n - second + 1];
  if (first > second) swap(first, second);
  return RMQ(g, first + 1, second);
}
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[n - i] - 'a' + 1;
    memcpy(sum[i], sum[i - 1], sizeof sum[0]);
    ++sum[i][s[i - 1] - 'a'];
  }
  build(a, rk2, n);
  init(h, g, n);
  for (int i = 1; i <= n; ++i) a[i] = s[i - 1] - 'a' + 1;
  build(a, rk, n);
  init(h, f, n);
  build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j + i <= n; j += i) {
      int p = 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 = lcs(j + i - 1, j + 2 * i - 1);
        if (!s) continue;
        s = min(s, i - 1);
        int p2 = 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 = 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 = lcp(l, r - i + 1);
        if (p >= i) return 1;
      }
      mx = min(n, rk[l] + Y);
      for (int i = max(1, rk[l] - Y); i <= mx; ++i) {
        int p = sa[i], t = r - p + 1;
        if (l <= p && p <= r && t * 2 <= len && 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");
  }
}

### Prompt

In cpp, your task is to solve the following 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.

### Response

```cpp
#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], rk[N], rk2[N], h[N], sa[N];
int sum[N][26], trL[N << 2], trR[N << 2];
char s[N];
const int Max_N = N;
namespace SA_IS {
int *sa;
template <typename _Char>
void push_S(const _Char s[], const int first, int cur[]) {
  sa[--cur[static_cast<int>(s[first])]] = first;
};
template <typename _Char>
void push_L(const _Char s[], const int first, int cur[]) {
  sa[cur[static_cast<int>(s[first])]++] = first;
};
template <typename _Char>
void induced_sort(const int v[], const int n, const int m, const _Char s[],
                  char type[], int cnt[], int n1) {
  std::fill(sa, sa + n, 0);
  int *cur = cnt + m;
  std::copy(cnt, cnt + m, cur);
  for (int i = n1 - 1; i >= 0; --i) push_S(s, v[i], cur);
  std::copy(cnt, cnt + m - 1, cur + 1);
  for (int i = 0; i < n; ++i)
    if (sa[i] > 0 && type[sa[i] - 1] == 0) push_L(s, sa[i] - 1, cur);
  std::copy(cnt, cnt + m, cur);
  for (int i = n - 1; i >= 0; --i)
    if (sa[i] > 0 && type[sa[i] - 1]) push_S(s, sa[i] - 1, cur);
}
template <typename _Char>
bool lms_equal(const _Char s[], char type[], int first, int second) {
  if (s[first] == s[second])
    while (s[++first] == s[++second] && type[first] == type[second])
      if (type[first] == 2 || type[second] == 2) return true;
  return false;
}
char *tp;
bool cmp(const int first) { return tp[first] != 2; }
template <typename _Char>
void sais_core(const int n, const int m, const _Char s[], char type[],
               int lms[], int cnt[]) {
  int n1 = 0, ch = -1;
  tp = type;
  type[n - 1] = 1;
  for (int i = n - 2; i >= 0; --i)
    type[i] = s[i] == s[i + 1] ? type[i + 1] : s[i] < s[i + 1];
  std::fill(cnt, cnt + m, 0);
  for (int i = 0; i < n; ++i) ++cnt[static_cast<int>(s[i])];
  std::partial_sum(cnt, cnt + m, cnt);
  for (int i = 1; i < n; ++i)
    if (type[i - 1] == 0 && type[i] == 1) type[i] = 2, lms[n1++] = i;
  induced_sort(lms, n, m, s, type, cnt, n1);
  int *s1 = std::remove_if(sa, sa + n, cmp);
  for (int i = 0; i < n1; ++i)
    s1[sa[i] >> 1] = ch += ch <= 0 || !lms_equal(s, type, sa[i], sa[i - 1]);
  for (int i = 0; i < n1; ++i) s1[i] = s1[lms[i] >> 1];
  if (ch + 1 < n1)
    sais_core(n1, ch + 1, s1, type + n, lms + n1, cnt + m);
  else
    for (int i = 0; i < n1; ++i) sa[s1[i]] = i;
  for (int i = 0; i < n1; ++i) lms[n1 + i] = lms[sa[i]];
  induced_sort(lms + n1, n, m, s, type, cnt, n1);
}
template <typename _Char>
void main(const _Char s[], const int n, const int m) {
  static int _lms[Max_N], _cnt[Max_N << 1];
  static char _type[Max_N << 1];
  sais_core(n + 1, m, s, _type, _lms, _cnt);
}
}  // namespace SA_IS
void calc(int *s, int *rk, int n) {
  for (int i = 1; i <= n; ++i) ++sa[i];
  for (int i = 1; i <= n; i++) rk[sa[i]] = i;
  for (int i = 1, j, k = 0; i <= n; i++) {
    if (rk[i] == 1) continue;
    if (k) k--;
    j = sa[rk[i] - 1];
    while (s[i + k] == s[j + k]) k++;
    h[rk[i]] = k;
  }
}
void build(int *a, int *rk, int n) {
  SA_IS::sa = sa;
  a[n + 1] = 0;
  SA_IS::main(a + 1, n, 128);
  calc(a, rk, n);
}
int f[20][N], g[20][N];
void init(int a[N], int f[20][N], int n) {
  Log[0] = -1;
  for (int i = 1; i <= n; ++i) f[0][i] = a[i], Log[i] = Log[i >> 1] + 1;
  for (int j = 1; j <= 19; ++j)
    for (int i = 0; i + (1 << j - 1) - 1 <= n; ++i) {
      f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
    }
}
int RMQ(int f[20][N], int l, int r) {
  int t = Log[r - l + 1];
  return min(f[t][l], f[t][r - (1 << t) + 1]);
}
int lcp(int first, int second) {
  first = rk[first], second = rk[second];
  if (first > second) swap(first, second);
  return RMQ(f, first + 1, second);
}
int lcs(int first, int second) {
  first = rk2[n - first + 1], second = rk2[n - second + 1];
  if (first > second) swap(first, second);
  return RMQ(g, first + 1, second);
}
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[n - i] - 'a' + 1;
    memcpy(sum[i], sum[i - 1], sizeof sum[0]);
    ++sum[i][s[i - 1] - 'a'];
  }
  build(a, rk2, n);
  init(h, g, n);
  for (int i = 1; i <= n; ++i) a[i] = s[i - 1] - 'a' + 1;
  build(a, rk, n);
  init(h, f, n);
  build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j + i <= n; j += i) {
      int p = 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 = lcs(j + i - 1, j + 2 * i - 1);
        if (!s) continue;
        s = min(s, i - 1);
        int p2 = 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 = 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 = lcp(l, r - i + 1);
        if (p >= i) return 1;
      }
      mx = min(n, rk[l] + Y);
      for (int i = max(1, rk[l] - Y); i <= mx; ++i) {
        int p = sa[i], t = r - p + 1;
        if (l <= p && p <= r && t * 2 <= len && 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");
  }
}

```