問題文

長さ $M$ の文字列 $X$ に対する操作を，以下のように定めます．

• 操作：$1 \leq i \leq M - 1$ を満たす整数 $i$ を $1$ つ選ぶ．$X$ の $i$ 文字目と $i+1$ 文字目を入れ替える．

$1$ から $9$ までの数字からなる文字列 $T$ に対して，$f(T)$ を次のように定めます．

• $T$ に対して操作を $0$ 回以上好きな回数行えるとき，$T$ を十進表記の整数として見たときに $8$ の倍数にするために必要な操作の回数の最小値．ただし，どのように操作を行っても不可能な場合は $f(T) = -1$ とする．

長さ $N$ の，$1$ から $9$ までの数字のみからなる文字列 $S$ が与えられます．

以下に示す $Q$ 個のクエリが与えられるので，それぞれに対して答えてください．

• クエリ $i$：$1 \leq l_i \leq r_i \leq N$ を満たす整数の組 $(l_i, r_i)$ が与えられる．$S$ の $l_i$ 文字目から $r_i$ 文字目までからなる部分文字列を $S[l_i, r_i]$ とするとき，$f(S[l_i, r_i])$ を求めよ．

制約

• $N, Q, l_i, r_i$ は整数
• $S$ は $1$ から $9$ までの数字からなる長さ $N$ の文字列
• $1 \leq N \leq 2.88 \times 10^5$
• $1 \leq Q \leq 2.88 \times 10^5$
• $1 \leq l_i \leq r_i \leq N$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $Q$
$S$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

出力

$Q$ 行出力せよ．$i \ (1 \leq i \leq Q)$ 行目には，$i$ 番目のクエリに対する答えを出力せよ．

サンプル

15 4
123456789111141
6 9
3 6
10 13
8 15

3
0
-1
7