//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

/*

定义dp(x,i,j)表示区间[0,x)内能够获得的2017的前缀长度为i的，至少要删除多少个字符

最少要删除多少个才能构成前缀为j的2017,然后我们不需要去管x，只需要用线段树去维护i，j即可。

*/

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

struct Node{

    int dp[][];

}tree[maxn << ];

int n, q;

char ch[maxn];

map<char, int> id;

inline void init(Node &t){

    for (int i = ; i < ; i++)

        for (int j = ; j < ; j++)

            t.dp[i][j] = inf;

}

Node Merge(Node a, Node b){

    Node tmp; init(tmp);

    for (int i = ; i <= ; i++)

        for (int j = i; j <= ; j++)

            for (int k = i; k <= j; k++)

                tmp.dp[i][j] = min(tmp.dp[i][j], a.dp[i][k] + b.dp[k][j]);

    return tmp;

}

void display(Node t){

    for (int i = ; i < ; i++){

        for (int j = ; j < ; j++)

            printf("%d ", t.dp[i][j]);

        cout << endl;

    }

}

void buildtree(int l, int r, int o){

    if (l == r){

        init(tree[o]);

        for (int i = ; i < ; i++)

            tree[o].dp[i][i] = ;

        int pos = id[ch[l]];

        if (pos <= ) tree[o].dp[pos][pos] = , tree[o].dp[pos][pos + ] = ;

        if (pos == ) tree[o].dp[][] = tree[o].dp[][] = ;

        return ;

    }

    int mid = (l + r) / ;

    if (l <= mid) buildtree(l, mid, o << );

    if (r > mid) buildtree(mid + , r, o <<  | );

    tree[o] = Merge(tree[o << ], tree[o <<  | ]);

    //display(tree[o]);

}

Node ans;

void query(int ql, int qr, int l, int r, int o){

    if (ql <= l && qr >= r) {

        if (ql == l) ans = tree[o];

        else ans = Merge(ans, tree[o]);

        return ;

    }

    int mid = (l + r) / ;

    if (ql <= mid) query(ql, qr, l, mid, o << );

    if (qr > mid) query(ql, qr, mid + , r, o <<  | );

}

int main(){

    int cnt = ;

    id[''] = , id[''] = , id[''] = , id[''] = , id[''] = ;

    for (char i = ''; i <= ''; i++) if(id.count(i) == ) id[i] = ++cnt;

    cin >> n >> q;

    scanf("%s", ch + );

    buildtree(, n, );

    for (int i = ; i <= q; i++){

        int ql, qr; scanf("%d%d", &ql, &qr);

        init(ans);

        query(ql, qr, , n, );

        if (ans.dp[][] >= inf) puts("-1");

        else printf("%d\n", ans.dp[][]);

    }

    return ;

}