#include <bits/stdc++.h>
using namespace std;
void getre() {
  int x = 0;
  printf("%d\n", 1 / x);
}
void gettle() {
  int res = 1;
  while (1) res <<= 1;
  printf("%d\n", res);
}
template <typename T, typename S>
inline bool upmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename N, typename PN>
inline N flo(N a, PN b) {
  return a >= 0 ? a / b : -((-a - 1) / b) - 1;
}
template <typename N, typename PN>
inline N cei(N a, PN b) {
  return a > 0 ? (a - 1) / b + 1 : -(-a / b);
}
template <typename N>
N gcd(N a, N b) {
  return b ? gcd(b, a % b) : a;
}
template <typename N>
inline int sgn(N a) {
  return a > 0 ? 1 : (a < 0 ? -1 : 0);
}
inline void gn(long long &x) {
  int sg = 1;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  c == '-' ? (sg = -1, x = 0) : (x = c - '0');
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= sg;
}
inline void gn(int &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(unsigned long long &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gn(long double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gs(char *s) { scanf("%s", s); }
inline void gc(char &c) {
  while ((c = getchar()) > 126 || c < 33)
    ;
}
inline void pc(char c) { putchar(c); }
inline long long sqr(long long a) { return a * a; }
inline double sqrf(double a) { return a * a; }
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846264338327950288L;
const double eps = 1e-6;
char s[222222];
struct node {
  int f[5][5];
} inn;
const int SEG_MAXN = 200000 + 5;
node seg[SEG_MAXN * 4];
int get(char c) {
  if (c == '2')
    return 1;
  else if (c == '0')
    return 2;
  else if (c == '1')
    return 3;
  else if (c == '6')
    return 4;
  else
    return 0;
}
node inis(char c) {
  int ind = get(c);
  node ret;
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++) {
      if (i > j)
        ret.f[i][j] = inf;
      else {
        if (ind == i + 1) {
          if (j == i)
            ret.f[i][j] = 1;
          else if (j == ind)
            ret.f[i][j] = 0;
          else
            ret.f[i][j] = inf;
        } else {
          if (j == i)
            ret.f[i][j] = 0;
          else
            ret.f[i][j] = inf;
        }
      }
    }
  return ret;
}
node operator+(const node &a, const node &b) {
  node c = inn;
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++)
      for (int k = (i), _ed = (j + 1); k < _ed; k++) {
        upmin(c.f[i][j], a.f[i][k] + b.f[k][j]);
      }
  return c;
}
inline void segpu(int x) { seg[x] = seg[x << 1] + seg[x << 1 | 1]; }
void seginit_in(int l, int r, int x) {
  if (l == r) {
    seg[x] = inis(s[l]);
  } else {
    int mid = l + r >> 1;
    seginit_in(l, mid, x << 1);
    seginit_in(mid + 1, r, x << 1 | 1);
    segpu(x);
  }
}
int l1, r1, I;
node sans;
bool ans_bo;
void segque_in(int l, int r, int x) {
  if (l1 <= l && r <= r1) {
    if (!ans_bo)
      ans_bo = 1, sans = seg[x];
    else
      sans = sans + seg[x];
  } else {
    int mid = l + r >> 1;
    if (l1 <= mid) segque_in(l, mid, x << 1);
    if (r1 > mid) segque_in(mid + 1, r, x << 1 | 1);
  }
}
int segn;
node segque(int l, int r) {
  if (l > r) return inn;
  ans_bo = 0, l1 = l, r1 = r;
  segque_in(1, segn, 1);
  return sans;
}
void seginit(int n) {
  segn = n;
  seginit_in(1, segn, 1);
}
int n;
int las7[222222];
int cnt6[222222];
int main() {
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++) inn.f[i][j] = inf;
  int q;
  gn(n);
  gn(q);
  gs(s + 1);
  for (int i = (1), _ed = (n + 1); i < _ed; i++) {
    if (s[i] == '7')
      las7[i] = i;
    else
      las7[i] = las7[i - 1];
  }
  for (int i = (1), _ed = (n + 1); i < _ed; i++) {
    if (s[i] == '6')
      cnt6[i] = cnt6[i - 1] + 1;
    else
      cnt6[i] = cnt6[i - 1];
  }
  seginit(n);
  while (q--) {
    int l, r;
    gn(l);
    gn(r);
    int pos7 = las7[r];
    if (pos7 < l) {
      printf("-1\n");
      continue;
    }
    int ans = cnt6[r] - cnt6[pos7];
    node ret = segque(l, pos7);
    int an = ret.f[0][3];
    if (an >= inf) {
      printf("-1\n");
    } else {
      printf("%d\n", ans + an);
    }
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is  - 1.

Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index ai and ending at the index bi (inclusive).

Input

The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.

The second line contains a string s of length n. Every character is one of digits '0'–'9'.

The i-th of next q lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n), describing a substring in the i-th query.

Output

For each query print the ugliness of the given substring.

Examples

Input

8 3
20166766
1 8
1 7
2 8


Output

4
3
-1


Input

15 5
012016662091670
3 4
1 14
4 15
1 13
10 15


Output

-1
2
1
-1
-1


Input

4 2
1234
2 4
1 2


Output

-1
-1

Note

In the first sample:

  * In the first query, ugliness("20166766") = 4 because all four sixes must be removed. 
  * In the second query, ugliness("2016676") = 3 because all three sixes must be removed. 
  * In the third query, ugliness("0166766") = - 1 because it's impossible to remove some digits to get a nice string. 



In the second sample:

  * In the second query, ugliness("01201666209167") = 2. It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice. 
  * In the third query, ugliness("016662091670") = 1. It's optimal to remove the last digit '6', what gives a nice string "01666209170". 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void getre() {
  int x = 0;
  printf("%d\n", 1 / x);
}
void gettle() {
  int res = 1;
  while (1) res <<= 1;
  printf("%d\n", res);
}
template <typename T, typename S>
inline bool upmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename N, typename PN>
inline N flo(N a, PN b) {
  return a >= 0 ? a / b : -((-a - 1) / b) - 1;
}
template <typename N, typename PN>
inline N cei(N a, PN b) {
  return a > 0 ? (a - 1) / b + 1 : -(-a / b);
}
template <typename N>
N gcd(N a, N b) {
  return b ? gcd(b, a % b) : a;
}
template <typename N>
inline int sgn(N a) {
  return a > 0 ? 1 : (a < 0 ? -1 : 0);
}
inline void gn(long long &x) {
  int sg = 1;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  c == '-' ? (sg = -1, x = 0) : (x = c - '0');
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= sg;
}
inline void gn(int &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(unsigned long long &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gn(long double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gs(char *s) { scanf("%s", s); }
inline void gc(char &c) {
  while ((c = getchar()) > 126 || c < 33)
    ;
}
inline void pc(char c) { putchar(c); }
inline long long sqr(long long a) { return a * a; }
inline double sqrf(double a) { return a * a; }
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846264338327950288L;
const double eps = 1e-6;
char s[222222];
struct node {
  int f[5][5];
} inn;
const int SEG_MAXN = 200000 + 5;
node seg[SEG_MAXN * 4];
int get(char c) {
  if (c == '2')
    return 1;
  else if (c == '0')
    return 2;
  else if (c == '1')
    return 3;
  else if (c == '6')
    return 4;
  else
    return 0;
}
node inis(char c) {
  int ind = get(c);
  node ret;
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++) {
      if (i > j)
        ret.f[i][j] = inf;
      else {
        if (ind == i + 1) {
          if (j == i)
            ret.f[i][j] = 1;
          else if (j == ind)
            ret.f[i][j] = 0;
          else
            ret.f[i][j] = inf;
        } else {
          if (j == i)
            ret.f[i][j] = 0;
          else
            ret.f[i][j] = inf;
        }
      }
    }
  return ret;
}
node operator+(const node &a, const node &b) {
  node c = inn;
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++)
      for (int k = (i), _ed = (j + 1); k < _ed; k++) {
        upmin(c.f[i][j], a.f[i][k] + b.f[k][j]);
      }
  return c;
}
inline void segpu(int x) { seg[x] = seg[x << 1] + seg[x << 1 | 1]; }
void seginit_in(int l, int r, int x) {
  if (l == r) {
    seg[x] = inis(s[l]);
  } else {
    int mid = l + r >> 1;
    seginit_in(l, mid, x << 1);
    seginit_in(mid + 1, r, x << 1 | 1);
    segpu(x);
  }
}
int l1, r1, I;
node sans;
bool ans_bo;
void segque_in(int l, int r, int x) {
  if (l1 <= l && r <= r1) {
    if (!ans_bo)
      ans_bo = 1, sans = seg[x];
    else
      sans = sans + seg[x];
  } else {
    int mid = l + r >> 1;
    if (l1 <= mid) segque_in(l, mid, x << 1);
    if (r1 > mid) segque_in(mid + 1, r, x << 1 | 1);
  }
}
int segn;
node segque(int l, int r) {
  if (l > r) return inn;
  ans_bo = 0, l1 = l, r1 = r;
  segque_in(1, segn, 1);
  return sans;
}
void seginit(int n) {
  segn = n;
  seginit_in(1, segn, 1);
}
int n;
int las7[222222];
int cnt6[222222];
int main() {
  for (int i = (0), _ed = (5); i < _ed; i++)
    for (int j = (0), _ed = (5); j < _ed; j++) inn.f[i][j] = inf;
  int q;
  gn(n);
  gn(q);
  gs(s + 1);
  for (int i = (1), _ed = (n + 1); i < _ed; i++) {
    if (s[i] == '7')
      las7[i] = i;
    else
      las7[i] = las7[i - 1];
  }
  for (int i = (1), _ed = (n + 1); i < _ed; i++) {
    if (s[i] == '6')
      cnt6[i] = cnt6[i - 1] + 1;
    else
      cnt6[i] = cnt6[i - 1];
  }
  seginit(n);
  while (q--) {
    int l, r;
    gn(l);
    gn(r);
    int pos7 = las7[r];
    if (pos7 < l) {
      printf("-1\n");
      continue;
    }
    int ans = cnt6[r] - cnt6[pos7];
    node ret = segque(l, pos7);
    int an = ret.f[0][3];
    if (an >= inf) {
      printf("-1\n");
    } else {
      printf("%d\n", ans + an);
    }
  }
  return 0;
}

```