#include <cstdio>
#include <algorithm>

#define DIM 610
#define INF 2000000000
using namespace std;

int N, Q, X, Y;
int Answer[DIM][DIM];
int D[5][DIM];
char String[DIM], ch;

int main ()
{
    freopen ("perb.in" ,"r", stdin );
    freopen ("perb.out","w", stdout);

    scanf ("%d %d", &N, &Q );
    scanf ("%c", &ch);

    for (int i = 1; i <= N; i ++)
        scanf ("%c", &String[i]);

    for (int i = 1; i <= N; i ++)
        for (int j = i; j <= N; j ++)
            Answer[i][j] = -1;

    for (int k = N / 2; k >= 1; k --) {

        for (int p = 1; p <= N; p ++) {
            if (String[p] == 'A') { D[1][p] = 0; D[2][p] = 1; D[3][p] = 1; D[4][p] = 1; }
            if (String[p] == 'C') { D[1][p] = 1; D[2][p] = 0; D[3][p] = 1; D[4][p] = 1; }
            if (String[p] == 'G') { D[1][p] = 1; D[2][p] = 1; D[3][p] = 0; D[4][p] = 1; }
            if (String[p] == 'T') { D[1][p] = 1; D[2][p] = 1; D[3][p] = 1; D[4][p] = 0; }

            if (p >= k) {
                D[1][p] += D[1][p-k];
                D[2][p] += D[2][p-k];
                D[3][p] += D[3][p-k];
                D[4][p] += D[4][p-k];
            }
        }

        for (int i = 1; i <= N-k+1; i ++) {
            for (int j = i+k-1; j <= N; j += k) {
                if (Answer[i][j] == -1) {
                    for (int p = j-k+1; p <= j; p ++) {

                        int val = INF;
                        val = min (D[1][p] - D[1][max(0, i-j+p-1)], val);
                        val = min (D[2][p] - D[2][max(0, i-j+p-1)], val);
                        val = min (D[3][p] - D[3][max(0, i-j+p-1)], val);
                        val = min (D[4][p] - D[4][max(0, i-j+p-1)], val);

                        Answer[i][j] += val;
                    }
                }
            }
        }
    }

    for (int q = 1; q <= Q; q ++) {
        scanf  ("%d %d", &X, &Y);
        printf ("%d\n" , Answer[X][Y] + 1);
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}