#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
const int INF = 1e9;
const int mc = 5;
int n, q;
string s;
struct SS {
  int a[mc][mc];
};
struct SS digits[10];
struct SS identity;
struct SS combine(struct SS& a, struct SS& b) {
  struct SS c;
  for (int x = 0; x < mc; x++) {
    for (int y = 0; y < mc; y++) {
      int ans = INF;
      for (int z = 0; z < mc; z++) {
        int aa = a.a[x][z];
        int bb = b.a[z][y];
        if (aa >= INF || bb >= INF) continue;
        chkmin(ans, aa + bb);
      }
      c.a[x][y] = ans;
    }
  }
  return c;
}
const int MAXN = 2e5 + 4;
struct SS t[2 * MAXN];
void build(int n) {
  for (int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
struct SS query(int l, int r, int n) {
  r++;
  struct SS resl = identity, resr = identity;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) resl = combine(resl, t[l++]);
    if (r & 1) resr = combine(t[--r], resr);
  }
  return combine(resl, resr);
}
class TaskE {
 public:
  void solve(std::istream& in, std::ostream& out) {
    cin.tie(0);
    ios::sync_with_stdio(0);
    in >> n >> q;
    in >> s;
    for (int x = 0; x < mc; x++)
      for (int y = 0; y < mc; y++) identity.a[x][y] = (x == y) ? 0 : INF;
    for (int d = 0; d < 10; d++) {
      struct SS t;
      for (int x = 0; x < mc; x++)
        for (int y = 0; y < mc; y++) t.a[x][y] = INF;
      {
        int x = 0;
        if (d == 2) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 1;
        if (d == 0) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 2;
        if (d == 1) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 3;
        if (d == 7) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else if (d == 6) {
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 4;
        if (d == 6) {
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      digits[d] = t;
    }
    for (int i = 0; i < n; i++) {
      int d = s[i] - '0';
      t[n + i] = digits[d];
    }
    build(n);
    for (int i = 0; i < q; i++) {
      int l, r;
      in >> l >> r;
      --l;
      --r;
      struct SS ans = query(l, r, n);
      int final = ans.a[0][4];
      if (final >= INF) final = -1;
      out << final << endl;
    }
  }
};
int main() {
  TaskE solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

### Prompt

Generate 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;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
const int INF = 1e9;
const int mc = 5;
int n, q;
string s;
struct SS {
  int a[mc][mc];
};
struct SS digits[10];
struct SS identity;
struct SS combine(struct SS& a, struct SS& b) {
  struct SS c;
  for (int x = 0; x < mc; x++) {
    for (int y = 0; y < mc; y++) {
      int ans = INF;
      for (int z = 0; z < mc; z++) {
        int aa = a.a[x][z];
        int bb = b.a[z][y];
        if (aa >= INF || bb >= INF) continue;
        chkmin(ans, aa + bb);
      }
      c.a[x][y] = ans;
    }
  }
  return c;
}
const int MAXN = 2e5 + 4;
struct SS t[2 * MAXN];
void build(int n) {
  for (int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
struct SS query(int l, int r, int n) {
  r++;
  struct SS resl = identity, resr = identity;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) resl = combine(resl, t[l++]);
    if (r & 1) resr = combine(t[--r], resr);
  }
  return combine(resl, resr);
}
class TaskE {
 public:
  void solve(std::istream& in, std::ostream& out) {
    cin.tie(0);
    ios::sync_with_stdio(0);
    in >> n >> q;
    in >> s;
    for (int x = 0; x < mc; x++)
      for (int y = 0; y < mc; y++) identity.a[x][y] = (x == y) ? 0 : INF;
    for (int d = 0; d < 10; d++) {
      struct SS t;
      for (int x = 0; x < mc; x++)
        for (int y = 0; y < mc; y++) t.a[x][y] = INF;
      {
        int x = 0;
        if (d == 2) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 1;
        if (d == 0) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 2;
        if (d == 1) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 3;
        if (d == 7) {
          t.a[x][x + 1] = 0;
          t.a[x][x] = 1;
        } else if (d == 6) {
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      {
        int x = 4;
        if (d == 6) {
          t.a[x][x] = 1;
        } else {
          t.a[x][x] = 0;
        }
      }
      digits[d] = t;
    }
    for (int i = 0; i < n; i++) {
      int d = s[i] - '0';
      t[n + i] = digits[d];
    }
    build(n);
    for (int i = 0; i < q; i++) {
      int l, r;
      in >> l >> r;
      --l;
      --r;
      struct SS ans = query(l, r, n);
      int final = ans.a[0][4];
      if (final >= INF) final = -1;
      out << final << endl;
    }
  }
};
int main() {
  TaskE solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

```