#include <bits/stdc++.h>
using namespace std;
struct debug_t {
  template <typename T>
  debug_t& operator<<(const T& value) {
    return *this;
  }
  debug_t& write(const char data[], streamsize n) { return *this; }
} debug;
enum {
  I00,
  I01,
  I02,
  I03,
  I04,
  I11,
  I12,
  I13,
  I14,
  I22,
  I23,
  I24,
  I33,
  I34,
  I44,
};
struct Matrix {
  int mx[15];
  int& operator[](int i) { return mx[i]; }
  int operator[](int i) const { return mx[i]; }
  Matrix& operator|=(const Matrix& rhs) {
    mx[I44] = min(0x3F3F3F3F, mx[I44] + rhs[I44]);
    mx[I34] = min(0x3F3F3F3F, min(mx[I33] + rhs[I34], mx[I34] + rhs[I44]));
    mx[I33] = min(0x3F3F3F3F, mx[I33] + rhs[I33]);
    mx[I24] = min(0x3F3F3F3F, min(mx[I22] + rhs[I24],
                                  min(mx[I23] + rhs[I34], mx[I24] + rhs[I44])));
    mx[I23] = min(mx[I22] + rhs[I23], mx[I23] + rhs[I33]);
    mx[I22] = min(0x3F3F3F3F, mx[I22] + rhs[I22]);
    mx[I14] =
        min(0x3F3F3F3F, min(mx[I11] + rhs[I14],
                            min(mx[I12] + rhs[I24],
                                min(mx[I13] + rhs[I34], mx[I14] + rhs[I44]))));
    mx[I13] = min(0x3F3F3F3F, min(mx[I11] + rhs[I13],
                                  min(mx[I12] + rhs[I23], mx[I13] + rhs[I33])));
    mx[I12] = min(0x3F3F3F3F, min(mx[I11] + rhs[I12], mx[I12] + rhs[I22]));
    mx[I11] = min(0x3F3F3F3F, mx[I11] + rhs[I11]);
    mx[I04] = min(0x3F3F3F3F,
                  min(mx[I00] + rhs[I04],
                      min(mx[I01] + rhs[I14],
                          min(mx[I02] + rhs[I24],
                              min(mx[I03] + rhs[I34], mx[I04] + rhs[I44])))));
    mx[I03] =
        min(0x3F3F3F3F, min(mx[I00] + rhs[I03],
                            min(mx[I01] + rhs[I13],
                                min(mx[I02] + rhs[I23], mx[I03] + rhs[I33]))));
    mx[I02] = min(0x3F3F3F3F, min(mx[I00] + rhs[I02],
                                  min(mx[I01] + rhs[I12], mx[I02] + rhs[I22])));
    mx[I01] = min(0x3F3F3F3F, min(mx[I00] + rhs[I01], mx[I01] + rhs[I11]));
    mx[I00] = min(0x3F3F3F3F, mx[I00] + rhs[I00]);
    return *this;
  }
};
Matrix mxdef;
template <int N>
struct SegTree {
  Matrix t[N << 2];
  static int lc(int i) { return i << 1 | 0x1; }
  static int rc(int i) { return (i << 1) + 2; }
  void init(int i, int lb, int rb, const Matrix a[]) {
    if (rb - lb == 1)
      t[i] = a[lb];
    else {
      const auto mid = (lb + rb) >> 1;
      init(lc(i), lb, mid, a);
      init(rc(i), mid, rb, a);
      t[i] = t[lc(i)];
      t[i] |= t[rc(i)];
    }
  }
  void getMin(int i, int lb, int rb, int left, int right,
              Matrix& result) const {
    if (left >= right)
      result = mxdef;
    else if (lb == left && rb == right)
      result = t[i];
    else {
      Matrix temp;
      const auto mid = (lb + rb) >> 1;
      getMin(lc(i), lb, mid, left, min(mid, right), result);
      getMin(rc(i), mid, rb, max(left, mid), right, temp);
      result |= temp;
    }
  }
};
enum { N = (int)2e5 };
Matrix a[N];
SegTree<N> sgt;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Matrix mx2, mx0, mx1, mx7, mx6;
  memset(mx2.mx, 0x3F, sizeof mx2.mx);
  memset(mx0.mx, 0x3F, sizeof mx0.mx);
  memset(mx1.mx, 0x3F, sizeof mx1.mx);
  memset(mx7.mx, 0x3F, sizeof mx7.mx);
  memset(mx6.mx, 0x3F, sizeof mx6.mx);
  memset(mxdef.mx, 0x3F, sizeof mxdef.mx);
  mx2[I00] = 1;
  mx2[I01] = 0;
  mx2[I11] = 0;
  mx2[I22] = 0;
  mx2[I33] = 0;
  mx2[I44] = 0;
  mx0[I00] = 0;
  mx0[I11] = 1;
  mx0[I12] = 0;
  mx0[I22] = 0;
  mx0[I33] = 0;
  mx0[I44] = 0;
  mx1[I00] = 0;
  mx1[I11] = 0;
  mx1[I22] = 1;
  mx1[I23] = 0;
  mx1[I33] = 0;
  mx1[I44] = 0;
  mx7[I00] = 0;
  mx7[I11] = 0;
  mx7[I22] = 0;
  mx7[I33] = 1;
  mx7[I34] = 0;
  mx7[I44] = 0;
  mx6[I00] = 0;
  mx6[I11] = 0;
  mx6[I22] = 0;
  mx6[I33] = 1;
  mx6[I44] = 1;
  mxdef[I00] = 0;
  mxdef[I11] = 0;
  mxdef[I22] = 0;
  mxdef[I33] = 0;
  mxdef[I44] = 0;
  int n, q;
  while (cin >> n >> q) {
    for (int i = 0; i < n; i++) {
      char c;
      cin >> c;
      switch (c) {
        case '0':
          a[i] = mx0;
          break;
        case '1':
          a[i] = mx1;
          break;
        case '2':
          a[i] = mx2;
          break;
        case '6':
          a[i] = mx6;
          break;
        case '7':
          a[i] = mx7;
          break;
        default:
          a[i] = mxdef;
      }
    }
    sgt.init(0, 0, n, a);
    Matrix mx;
    while (q--) {
      int left, right;
      cin >> left >> right;
      left--;
      sgt.getMin(0, 0, n, left, right, mx);
      if (mx[I04] > right - left)
        cout << "-1\n";
      else
        cout << mx[I04] << '\n';
    }
    debug << '\n';
  }
}

### Prompt

Create a solution in Cpp for 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;
struct debug_t {
  template <typename T>
  debug_t& operator<<(const T& value) {
    return *this;
  }
  debug_t& write(const char data[], streamsize n) { return *this; }
} debug;
enum {
  I00,
  I01,
  I02,
  I03,
  I04,
  I11,
  I12,
  I13,
  I14,
  I22,
  I23,
  I24,
  I33,
  I34,
  I44,
};
struct Matrix {
  int mx[15];
  int& operator[](int i) { return mx[i]; }
  int operator[](int i) const { return mx[i]; }
  Matrix& operator|=(const Matrix& rhs) {
    mx[I44] = min(0x3F3F3F3F, mx[I44] + rhs[I44]);
    mx[I34] = min(0x3F3F3F3F, min(mx[I33] + rhs[I34], mx[I34] + rhs[I44]));
    mx[I33] = min(0x3F3F3F3F, mx[I33] + rhs[I33]);
    mx[I24] = min(0x3F3F3F3F, min(mx[I22] + rhs[I24],
                                  min(mx[I23] + rhs[I34], mx[I24] + rhs[I44])));
    mx[I23] = min(mx[I22] + rhs[I23], mx[I23] + rhs[I33]);
    mx[I22] = min(0x3F3F3F3F, mx[I22] + rhs[I22]);
    mx[I14] =
        min(0x3F3F3F3F, min(mx[I11] + rhs[I14],
                            min(mx[I12] + rhs[I24],
                                min(mx[I13] + rhs[I34], mx[I14] + rhs[I44]))));
    mx[I13] = min(0x3F3F3F3F, min(mx[I11] + rhs[I13],
                                  min(mx[I12] + rhs[I23], mx[I13] + rhs[I33])));
    mx[I12] = min(0x3F3F3F3F, min(mx[I11] + rhs[I12], mx[I12] + rhs[I22]));
    mx[I11] = min(0x3F3F3F3F, mx[I11] + rhs[I11]);
    mx[I04] = min(0x3F3F3F3F,
                  min(mx[I00] + rhs[I04],
                      min(mx[I01] + rhs[I14],
                          min(mx[I02] + rhs[I24],
                              min(mx[I03] + rhs[I34], mx[I04] + rhs[I44])))));
    mx[I03] =
        min(0x3F3F3F3F, min(mx[I00] + rhs[I03],
                            min(mx[I01] + rhs[I13],
                                min(mx[I02] + rhs[I23], mx[I03] + rhs[I33]))));
    mx[I02] = min(0x3F3F3F3F, min(mx[I00] + rhs[I02],
                                  min(mx[I01] + rhs[I12], mx[I02] + rhs[I22])));
    mx[I01] = min(0x3F3F3F3F, min(mx[I00] + rhs[I01], mx[I01] + rhs[I11]));
    mx[I00] = min(0x3F3F3F3F, mx[I00] + rhs[I00]);
    return *this;
  }
};
Matrix mxdef;
template <int N>
struct SegTree {
  Matrix t[N << 2];
  static int lc(int i) { return i << 1 | 0x1; }
  static int rc(int i) { return (i << 1) + 2; }
  void init(int i, int lb, int rb, const Matrix a[]) {
    if (rb - lb == 1)
      t[i] = a[lb];
    else {
      const auto mid = (lb + rb) >> 1;
      init(lc(i), lb, mid, a);
      init(rc(i), mid, rb, a);
      t[i] = t[lc(i)];
      t[i] |= t[rc(i)];
    }
  }
  void getMin(int i, int lb, int rb, int left, int right,
              Matrix& result) const {
    if (left >= right)
      result = mxdef;
    else if (lb == left && rb == right)
      result = t[i];
    else {
      Matrix temp;
      const auto mid = (lb + rb) >> 1;
      getMin(lc(i), lb, mid, left, min(mid, right), result);
      getMin(rc(i), mid, rb, max(left, mid), right, temp);
      result |= temp;
    }
  }
};
enum { N = (int)2e5 };
Matrix a[N];
SegTree<N> sgt;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Matrix mx2, mx0, mx1, mx7, mx6;
  memset(mx2.mx, 0x3F, sizeof mx2.mx);
  memset(mx0.mx, 0x3F, sizeof mx0.mx);
  memset(mx1.mx, 0x3F, sizeof mx1.mx);
  memset(mx7.mx, 0x3F, sizeof mx7.mx);
  memset(mx6.mx, 0x3F, sizeof mx6.mx);
  memset(mxdef.mx, 0x3F, sizeof mxdef.mx);
  mx2[I00] = 1;
  mx2[I01] = 0;
  mx2[I11] = 0;
  mx2[I22] = 0;
  mx2[I33] = 0;
  mx2[I44] = 0;
  mx0[I00] = 0;
  mx0[I11] = 1;
  mx0[I12] = 0;
  mx0[I22] = 0;
  mx0[I33] = 0;
  mx0[I44] = 0;
  mx1[I00] = 0;
  mx1[I11] = 0;
  mx1[I22] = 1;
  mx1[I23] = 0;
  mx1[I33] = 0;
  mx1[I44] = 0;
  mx7[I00] = 0;
  mx7[I11] = 0;
  mx7[I22] = 0;
  mx7[I33] = 1;
  mx7[I34] = 0;
  mx7[I44] = 0;
  mx6[I00] = 0;
  mx6[I11] = 0;
  mx6[I22] = 0;
  mx6[I33] = 1;
  mx6[I44] = 1;
  mxdef[I00] = 0;
  mxdef[I11] = 0;
  mxdef[I22] = 0;
  mxdef[I33] = 0;
  mxdef[I44] = 0;
  int n, q;
  while (cin >> n >> q) {
    for (int i = 0; i < n; i++) {
      char c;
      cin >> c;
      switch (c) {
        case '0':
          a[i] = mx0;
          break;
        case '1':
          a[i] = mx1;
          break;
        case '2':
          a[i] = mx2;
          break;
        case '6':
          a[i] = mx6;
          break;
        case '7':
          a[i] = mx7;
          break;
        default:
          a[i] = mxdef;
      }
    }
    sgt.init(0, 0, n, a);
    Matrix mx;
    while (q--) {
      int left, right;
      cin >> left >> right;
      left--;
      sgt.getMin(0, 0, n, left, right, mx);
      if (mx[I04] > right - left)
        cout << "-1\n";
      else
        cout << mx[I04] << '\n';
    }
    debug << '\n';
  }
}

```