#include <bits/stdc++.h>
using namespace std;
string DBG_DLM(int& i) { return (i++ == 0 ? "" : ", "); }
template <class T>
ostream& operator<<(ostream& os, vector<T> v);
template <class T>
ostream& operator<<(ostream& os, set<T> v);
template <class T>
ostream& operator<<(ostream& os, queue<T> q);
template <class T>
ostream& operator<<(ostream& os, priority_queue<T> q);
template <class T, class K>
ostream& operator<<(ostream& os, pair<T, K> p);
template <class T, class K>
ostream& operator<<(ostream& os, map<T, K> mp);
template <class T, class K>
ostream& operator<<(ostream& os, unordered_map<T, K> mp);
template <int I, class TPL>
void DBG(ostream& os, TPL t) {}
template <int I, class TPL, class H, class... Ts>
void DBG(ostream& os, TPL t) {
  os << (I == 0 ? "" : ", ") << get<I>(t);
  DBG<I + 1, TPL, Ts...>(os, t);
}
template <class T, class K>
void DBG(ostream& os, pair<T, K> p, string delim) {
  os << "(" << p.first << delim << p.second << ")";
}
template <class... Ts>
ostream& operator<<(ostream& os, tuple<Ts...> t) {
  os << "(";
  DBG<0, tuple<Ts...>, Ts...>(os, t);
  os << ")";
  return os;
}
template <class T, class K>
ostream& operator<<(ostream& os, pair<T, K> p) {
  DBG(os, p, ", ");
  return os;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& t : v) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, set<T> s) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& t : s) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.front();
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, priority_queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.top();
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream& operator<<(ostream& os, map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream& operator<<(ostream& os, unordered_map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vs = vector<string>;
using vvs = vector<vs>;
using vvvs = vector<vvs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vvvpii = vector<vvpii>;
template <class A, class B>
bool amax(A& a, const B& b) {
  return b > a ? a = b, 1 : 0;
}
template <class A, class B>
bool amin(A& a, const B& b) {
  return b < a ? a = b, 1 : 0;
}
ll ri() {
  ll l;
  cin >> l;
  return l;
}
string rs() {
  string s;
  cin >> s;
  return s;
}
template <class T, int N>
struct matrix_ {
  T val[N][N];
  matrix_(vector<vector<T>> ini) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) val[i][j] = ini[i][j];
  }
  matrix_(int d = 0) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) val[i][j] = T((i == j) * d);
  }
  T& at(int row, int col) { return val[row][col]; }
  const T& at(int row, int col) const { return val[row][col]; }
};
template <class T, int N>
ostream& operator<<(ostream& os, const matrix_<T, N>& mat) {
  vector<vector<T>> vec(N, vector<T>(N));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) vec[i][j] = mat.at(i, j);
  os << vec;
  return os;
}
using Mat = matrix_<int, 5>;
const int inf = 268435456;
const Mat MAX({{inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf}});
const Mat UNIT({{0, inf, inf, inf, inf},
                {inf, 0, inf, inf, inf},
                {inf, inf, 0, inf, inf},
                {inf, inf, inf, 0, inf},
                {inf, inf, inf, inf, 0}});
static const Mat def = UNIT;
struct SegTree0 {
  using V = Mat;
  const int n;
  vector<V> val;
  SegTree0(int _n) : n(p2(_n)), val(n * 2, def) {}
  V query(int a, int b) { return query(a, b, 0, 0, n); }
  void update(int i, V v) {
    i += n - 1;
    val[i] = v;
    while (i > 0) {
      i = (i - 1) / 2;
      val[i] = merge(val[i * 2 + 1], val[i * 2 + 2]);
    }
  }

 private:
  V query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return def;
    if (a <= l && r <= b) return val[k];
    return merge(query(a, b, k * 2 + 1, l, (l + r) / 2),
                 query(a, b, k * 2 + 2, (l + r) / 2, r));
  }
  static int p2(int n, int m = 1) { return m >= n ? m : p2(n, m * 2); }
  static V merge(const V& l, const V& r) {
    Mat ret = MAX;
    for (int i = int(0); i < int(5); ++i)
      for (int k = int(i); k < int(5); ++k)
        for (int j = int(k); j < int(5); ++j) {
          ret.val[i][j] = min(ret.val[i][j], l.val[i][k] + r.val[k][j]);
        }
    return ret;
  }
};
template <class V, class Merge>
struct SegmentTree {
  const int n;
  const V unit_value;
  vector<V> val;
  SegmentTree(int _n)
      : n(1 << (33 - __builtin_clz(_n - 1))),
        unit_value(Merge::unit()),
        val(n, unit_value) {}
  V get(int i) const { return val[i + n / 2]; }
  void set(int i, const V& v) { val[i + n / 2] = v; }
  void build() {
    for (int i = n / 2 - 1; i > 0; i--)
      val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);
  }
  void update(int i, const V& v) {
    i += n / 2;
    val[i] = v;
    while (i > 1) {
      i >>= 1;
      val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);
    }
  }
  V query(int l, int r) const {
    l = max(0, min(n / 2, l)) + n / 2;
    r = max(0, min(n / 2, r)) + n / 2;
    V ret = unit_value;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = Merge::merge(ret, val[l++]);
      if (r & 1) ret = Merge::merge(ret, val[--r]);
    }
    return ret;
  }
};
template <class V, class Merge>
ostream& operator<<(ostream& os, const SegmentTree<V, Merge>& seg) {
  vector<V> vec;
  for (int i = 0; i < seg.n; i++) {
    vec.emplace_back(seg.get(i));
  }
  os << vec;
  return os;
}
struct Merge {
  static Mat merge(const Mat& l, const Mat& r) {
    Mat ret = MAX;
    for (int i = int(0); i < int(5); ++i)
      for (int k = int(i); k < int(5); ++k)
        for (int j = int(k); j < int(5); ++j) {
          ret.val[i][j] = min(ret.val[i][j], l.val[i][k] + r.val[k][j]);
        }
    return ret;
  }
  static Mat unit() { return UNIT; }
};
using SegTree = SegmentTree<Mat, Merge>;
void Main() {
  int n = ri(), q = ri();
  auto s = rs();
  SegTree0 seg(n);
  for (int i = int(0); i < int(n); ++i) {
    const int d = s[i] - '0';
    Mat mat(UNIT);
    if (d == 2) {
      mat.at(0, 0) = 1;
      mat.at(0, 1) = 0;
    } else if (d == 0) {
      mat.at(1, 1) = 1;
      mat.at(1, 2) = 0;
    } else if (d == 1) {
      mat.at(2, 2) = 1;
      mat.at(2, 3) = 0;
    } else if (d == 7) {
      mat.at(3, 4) = 0;
    } else if (d == 6) {
      mat.at(3, 3) = 1;
      mat.at(4, 4) = 1;
    }
    seg.update(i, mat);
  }
  for (int i = int(0); i < int(n); ++i) {
  }
  for (int _ = int(0); _ < int(q); ++_) {
    int l = ri() - 1, r = ri() - 1 + 1;
    Mat ret = seg.query(l, r);
    int ans = ret.at(0, 4);
    if (ans == inf)
      cout << "-1\n";
    else
      cout << ans << "\n";
  }
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  Main();
  return 0;
}

### Prompt

Your challenge is to write 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;
string DBG_DLM(int& i) { return (i++ == 0 ? "" : ", "); }
template <class T>
ostream& operator<<(ostream& os, vector<T> v);
template <class T>
ostream& operator<<(ostream& os, set<T> v);
template <class T>
ostream& operator<<(ostream& os, queue<T> q);
template <class T>
ostream& operator<<(ostream& os, priority_queue<T> q);
template <class T, class K>
ostream& operator<<(ostream& os, pair<T, K> p);
template <class T, class K>
ostream& operator<<(ostream& os, map<T, K> mp);
template <class T, class K>
ostream& operator<<(ostream& os, unordered_map<T, K> mp);
template <int I, class TPL>
void DBG(ostream& os, TPL t) {}
template <int I, class TPL, class H, class... Ts>
void DBG(ostream& os, TPL t) {
  os << (I == 0 ? "" : ", ") << get<I>(t);
  DBG<I + 1, TPL, Ts...>(os, t);
}
template <class T, class K>
void DBG(ostream& os, pair<T, K> p, string delim) {
  os << "(" << p.first << delim << p.second << ")";
}
template <class... Ts>
ostream& operator<<(ostream& os, tuple<Ts...> t) {
  os << "(";
  DBG<0, tuple<Ts...>, Ts...>(os, t);
  os << ")";
  return os;
}
template <class T, class K>
ostream& operator<<(ostream& os, pair<T, K> p) {
  DBG(os, p, ", ");
  return os;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& t : v) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, set<T> s) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& t : s) {
        os << DBG_DLM(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.front();
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
ostream& operator<<(ostream& os, priority_queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << DBG_DLM(i) << q.top();
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream& operator<<(ostream& os, map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
ostream& operator<<(ostream& os, unordered_map<T, K> m) {
  {
    int i = 0;
    os << "{";
    {
      for (auto&& p : m) {
        os << DBG_DLM(i);
        DBG(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vs = vector<string>;
using vvs = vector<vs>;
using vvvs = vector<vvs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vvvpii = vector<vvpii>;
template <class A, class B>
bool amax(A& a, const B& b) {
  return b > a ? a = b, 1 : 0;
}
template <class A, class B>
bool amin(A& a, const B& b) {
  return b < a ? a = b, 1 : 0;
}
ll ri() {
  ll l;
  cin >> l;
  return l;
}
string rs() {
  string s;
  cin >> s;
  return s;
}
template <class T, int N>
struct matrix_ {
  T val[N][N];
  matrix_(vector<vector<T>> ini) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) val[i][j] = ini[i][j];
  }
  matrix_(int d = 0) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) val[i][j] = T((i == j) * d);
  }
  T& at(int row, int col) { return val[row][col]; }
  const T& at(int row, int col) const { return val[row][col]; }
};
template <class T, int N>
ostream& operator<<(ostream& os, const matrix_<T, N>& mat) {
  vector<vector<T>> vec(N, vector<T>(N));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) vec[i][j] = mat.at(i, j);
  os << vec;
  return os;
}
using Mat = matrix_<int, 5>;
const int inf = 268435456;
const Mat MAX({{inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf},
               {inf, inf, inf, inf, inf}});
const Mat UNIT({{0, inf, inf, inf, inf},
                {inf, 0, inf, inf, inf},
                {inf, inf, 0, inf, inf},
                {inf, inf, inf, 0, inf},
                {inf, inf, inf, inf, 0}});
static const Mat def = UNIT;
struct SegTree0 {
  using V = Mat;
  const int n;
  vector<V> val;
  SegTree0(int _n) : n(p2(_n)), val(n * 2, def) {}
  V query(int a, int b) { return query(a, b, 0, 0, n); }
  void update(int i, V v) {
    i += n - 1;
    val[i] = v;
    while (i > 0) {
      i = (i - 1) / 2;
      val[i] = merge(val[i * 2 + 1], val[i * 2 + 2]);
    }
  }

 private:
  V query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return def;
    if (a <= l && r <= b) return val[k];
    return merge(query(a, b, k * 2 + 1, l, (l + r) / 2),
                 query(a, b, k * 2 + 2, (l + r) / 2, r));
  }
  static int p2(int n, int m = 1) { return m >= n ? m : p2(n, m * 2); }
  static V merge(const V& l, const V& r) {
    Mat ret = MAX;
    for (int i = int(0); i < int(5); ++i)
      for (int k = int(i); k < int(5); ++k)
        for (int j = int(k); j < int(5); ++j) {
          ret.val[i][j] = min(ret.val[i][j], l.val[i][k] + r.val[k][j]);
        }
    return ret;
  }
};
template <class V, class Merge>
struct SegmentTree {
  const int n;
  const V unit_value;
  vector<V> val;
  SegmentTree(int _n)
      : n(1 << (33 - __builtin_clz(_n - 1))),
        unit_value(Merge::unit()),
        val(n, unit_value) {}
  V get(int i) const { return val[i + n / 2]; }
  void set(int i, const V& v) { val[i + n / 2] = v; }
  void build() {
    for (int i = n / 2 - 1; i > 0; i--)
      val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);
  }
  void update(int i, const V& v) {
    i += n / 2;
    val[i] = v;
    while (i > 1) {
      i >>= 1;
      val[i] = Merge::merge(val[i * 2 + 0], val[i * 2 + 1]);
    }
  }
  V query(int l, int r) const {
    l = max(0, min(n / 2, l)) + n / 2;
    r = max(0, min(n / 2, r)) + n / 2;
    V ret = unit_value;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret = Merge::merge(ret, val[l++]);
      if (r & 1) ret = Merge::merge(ret, val[--r]);
    }
    return ret;
  }
};
template <class V, class Merge>
ostream& operator<<(ostream& os, const SegmentTree<V, Merge>& seg) {
  vector<V> vec;
  for (int i = 0; i < seg.n; i++) {
    vec.emplace_back(seg.get(i));
  }
  os << vec;
  return os;
}
struct Merge {
  static Mat merge(const Mat& l, const Mat& r) {
    Mat ret = MAX;
    for (int i = int(0); i < int(5); ++i)
      for (int k = int(i); k < int(5); ++k)
        for (int j = int(k); j < int(5); ++j) {
          ret.val[i][j] = min(ret.val[i][j], l.val[i][k] + r.val[k][j]);
        }
    return ret;
  }
  static Mat unit() { return UNIT; }
};
using SegTree = SegmentTree<Mat, Merge>;
void Main() {
  int n = ri(), q = ri();
  auto s = rs();
  SegTree0 seg(n);
  for (int i = int(0); i < int(n); ++i) {
    const int d = s[i] - '0';
    Mat mat(UNIT);
    if (d == 2) {
      mat.at(0, 0) = 1;
      mat.at(0, 1) = 0;
    } else if (d == 0) {
      mat.at(1, 1) = 1;
      mat.at(1, 2) = 0;
    } else if (d == 1) {
      mat.at(2, 2) = 1;
      mat.at(2, 3) = 0;
    } else if (d == 7) {
      mat.at(3, 4) = 0;
    } else if (d == 6) {
      mat.at(3, 3) = 1;
      mat.at(4, 4) = 1;
    }
    seg.update(i, mat);
  }
  for (int i = int(0); i < int(n); ++i) {
  }
  for (int _ = int(0); _ < int(q); ++_) {
    int l = ri() - 1, r = ri() - 1 + 1;
    Mat ret = seg.query(l, r);
    int ans = ret.at(0, 4);
    if (ans == inf)
      cout << "-1\n";
    else
      cout << ans << "\n";
  }
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  Main();
  return 0;
}

```