/* 下3桁を8の倍数にしたい。 時間制約的に、1000以下の8の倍数全探索は行けそう。 下3桁を固定する。下3桁の3文字をその位置に持ってくるための最小操作回数を求めたい。 各文字が存在する最も右の位置を見て、その距離の総和を足せば良い? */ #include using namespace std; #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for(ll i=0; i<(ll)(n); i++) template bool chmax(T& a, T b) { return a bool chmin(T& a, T b) { return a>b ? a=b, true : false; } using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using VI=vector; using VVI=vector; using VL=vector; using VVL=vector; using PL=pair; using VP=vector; using WG=vector>>; #ifdef LOCAL #include "./debug.hpp" #else #define debug(...) #define print_line #endif //---------------------------------------------------------- void solve() { ll N,Q; cin>>N>>Q; string S; cin>>S; //8の倍数 vector eights; for(ll t=0; t<1000; t+=8) { string s=to_string(t); while(s.size()<3) s="0"+s; reverse(ALL(s)); eights.push_back(s); } vector> idx(10); REP(i,N) idx[S[i]-'0'].insert(-i); REP(i,10) idx[i].insert(1); while(Q--) { ll l,r; cin>>l>>r; l--; if(r-l==1) { if(S[l]=='8') cout<<0<<'\n'; else cout<<-1<<'\n'; continue; } else if(r-l==2) { string str=S.substr(l,2); ll x=stoll(str); if(x%8==0) cout<<0<<'\n'; else { reverse(ALL(str)); x=stoll(str); if(x%8==0) cout<<1<<'\n'; else cout<<-1<<'\n'; } continue; } ll ans=INF; for(auto s: eights) { ll res=0; VI ch; REP(i,3) { int c=s[i]-'0'; int right=-(*idx[c].upper_bound(-r)); if(right==-1 || rightx) right--; int goal=r-1-i; res+=abs(goal-right); } chmin(ans,res); for(int x: ch) idx[S[x]-'0'].insert(-x); } if(ans==INF) ans=-1; cout<>T; while(T--) solve(); }