#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
struct ST {
  int c[5][5];
} st[202020 << 2];
int a[202020];
void pull(ST& now, const ST& lc, const ST& rc) {
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 5; j++) now.c[i][j] = 202020;
  for (int i = 0; i < 5; i++)
    for (int j = i; j < 5; j++)
      for (int k = j; k < 5; k++)
        now.c[i][k] = min(now.c[i][k], lc.c[i][j] + rc.c[j][k]);
}
void build_st(int no, int l, int r) {
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) st[no].c[i][j] = 202020;
    st[no].c[i][i] = 0;
  }
  if (l == r) {
    int x = a[l];
    if (x == 6) {
      st[no].c[3][3] = 1;
      st[no].c[4][4] = 1;
    } else if (x == 2) {
      st[no].c[0][0] = 1;
      st[no].c[0][1] = 0;
    } else if (x == 0) {
      st[no].c[1][1] = 1;
      st[no].c[1][2] = 0;
    } else if (x == 1) {
      st[no].c[2][2] = 1;
      st[no].c[2][3] = 0;
    } else if (x == 7) {
      st[no].c[3][3] = 1;
      st[no].c[3][4] = 0;
    } else
      assert(false);
    return;
  }
  build_st((no << 1), l, ((l + r) >> 1));
  build_st((1 + (no << 1)), ((l + r) >> 1) + 1, r);
  pull(st[no], st[(no << 1)], st[(1 + (no << 1))]);
}
ST query(int no, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) return st[no];
  if (qr <= ((l + r) >> 1)) return query((no << 1), l, ((l + r) >> 1), ql, qr);
  if (((l + r) >> 1) < ql)
    return query((1 + (no << 1)), ((l + r) >> 1) + 1, r, ql, qr);
  ST lc = query((no << 1), l, ((l + r) >> 1), ql, ((l + r) >> 1));
  ST rc = query((1 + (no << 1)), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, qr);
  ST ret;
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) ret.c[i][j] = 202020;
    ret.c[i][i] = 0;
  }
  pull(ret, lc, rc);
  return ret;
}
void build() {}
int n, q, l[202020], r[202020], idx[202020], nn;
char c[202020];
void init() {
  scanf("%d%d", &n, &q);
  scanf("%s", c + 1);
  int ii = 0;
  for (int i = 1; i <= n; i++)
    if (c[i] <= '2' || c[i] == '6' || c[i] == '7') {
      idx[i] = ++ii;
      a[idx[i]] = c[i] - '0';
    }
  nn = ii;
  for (int i = n, lst = n + 1; i >= 1; i--) {
    if (idx[i]) lst = idx[i];
    l[i] = lst;
  }
  for (int i = 1, lst = 0; i <= n; i++) {
    if (idx[i]) lst = idx[i];
    r[i] = lst;
  }
}
void solve() {
  build_st(1, 1, nn);
  while (q--) {
    int ql = getint();
    int qr = getint();
    int qql = l[ql], qqr = r[qr];
    if (qqr - qql + 1 < 4) {
      puts("-1");
      continue;
    }
    ST ret = query(1, 1, nn, qql, qqr);
    int ans = ret.c[0][4];
    if (ans > n) ans = -1;
    printf("%d\n", ans);
  }
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
struct ST {
  int c[5][5];
} st[202020 << 2];
int a[202020];
void pull(ST& now, const ST& lc, const ST& rc) {
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 5; j++) now.c[i][j] = 202020;
  for (int i = 0; i < 5; i++)
    for (int j = i; j < 5; j++)
      for (int k = j; k < 5; k++)
        now.c[i][k] = min(now.c[i][k], lc.c[i][j] + rc.c[j][k]);
}
void build_st(int no, int l, int r) {
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) st[no].c[i][j] = 202020;
    st[no].c[i][i] = 0;
  }
  if (l == r) {
    int x = a[l];
    if (x == 6) {
      st[no].c[3][3] = 1;
      st[no].c[4][4] = 1;
    } else if (x == 2) {
      st[no].c[0][0] = 1;
      st[no].c[0][1] = 0;
    } else if (x == 0) {
      st[no].c[1][1] = 1;
      st[no].c[1][2] = 0;
    } else if (x == 1) {
      st[no].c[2][2] = 1;
      st[no].c[2][3] = 0;
    } else if (x == 7) {
      st[no].c[3][3] = 1;
      st[no].c[3][4] = 0;
    } else
      assert(false);
    return;
  }
  build_st((no << 1), l, ((l + r) >> 1));
  build_st((1 + (no << 1)), ((l + r) >> 1) + 1, r);
  pull(st[no], st[(no << 1)], st[(1 + (no << 1))]);
}
ST query(int no, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) return st[no];
  if (qr <= ((l + r) >> 1)) return query((no << 1), l, ((l + r) >> 1), ql, qr);
  if (((l + r) >> 1) < ql)
    return query((1 + (no << 1)), ((l + r) >> 1) + 1, r, ql, qr);
  ST lc = query((no << 1), l, ((l + r) >> 1), ql, ((l + r) >> 1));
  ST rc = query((1 + (no << 1)), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, qr);
  ST ret;
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) ret.c[i][j] = 202020;
    ret.c[i][i] = 0;
  }
  pull(ret, lc, rc);
  return ret;
}
void build() {}
int n, q, l[202020], r[202020], idx[202020], nn;
char c[202020];
void init() {
  scanf("%d%d", &n, &q);
  scanf("%s", c + 1);
  int ii = 0;
  for (int i = 1; i <= n; i++)
    if (c[i] <= '2' || c[i] == '6' || c[i] == '7') {
      idx[i] = ++ii;
      a[idx[i]] = c[i] - '0';
    }
  nn = ii;
  for (int i = n, lst = n + 1; i >= 1; i--) {
    if (idx[i]) lst = idx[i];
    l[i] = lst;
  }
  for (int i = 1, lst = 0; i <= n; i++) {
    if (idx[i]) lst = idx[i];
    r[i] = lst;
  }
}
void solve() {
  build_st(1, 1, nn);
  while (q--) {
    int ql = getint();
    int qr = getint();
    int qql = l[ql], qqr = r[qr];
    if (qqr - qql + 1 < 4) {
      puts("-1");
      continue;
    }
    ST ret = query(1, 1, nn, qql, qqr);
    int ans = ret.c[0][4];
    if (ans > n) ans = -1;
    printf("%d\n", ans);
  }
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```