#include <stdio.h>
#include <string.h>

#define LMAX 610

#define max(a, b) ((a) >= (b) ? (a) : (b))

int cnt[4], c[4][LMAX][LMAX], vmax;
int sol[LMAX][LMAX];
char s[LMAX];
int i, j, k, l, N, M, len, plen, qlen, csol;

void precompute() {
    memset(c, 0, sizeof(c));
    for (len = 1; len <= N; len++)
        for (i = 1; i <= N; i++) {
            if (i > len) {
                for (k = 0; k < 4; k++)
                    c[k][i][len] = c[k][i - len][len];
            }

            if (s[i] == 'A')
                c[0][i][len]++;
            else if (s[i] == 'C')
                c[1][i][len]++;
            else if (s[i] == 'G')
                c[2][i][len]++;
            else if (s[i] == 'T')
                c[3][i][len]++;
        }

    for (i = 1; i <= N; i++) {
        sol[i][i] = 0;

        for (j = i + 1; j <= N; j++) {
            sol[i][j] = (j - i + 1);

            for (len = 1; len * len <= (j - i + 1); len++) {
                if ((j - i + 1) % len > 0)
                    continue;

                // Considera perioada len.
                plen = len;
                qlen = (j - i + 1) / plen;

                csol = 0;
                for (k = j; k > j - plen; k--) {
                    memset(cnt, 0, sizeof(cnt));
                    vmax = 0;
                    for (l = 0; l < 4; l++) {
                        cnt[l] = c[l][k][plen] - c[l][max(k - (j - i + 1), 0)][plen];
                        if (cnt[l] > vmax)
                            vmax = cnt[l];
                    }

                    csol += (qlen - vmax);

                    if (csol >= sol[i][j])
                        break;
                }

                if (csol < sol[i][j])
                    sol[i][j] = csol;

                // Considera perioada (j - i + 1) / len;
                plen = (j - i + 1) / len;
                if ((plen < (j - i + 1)) && (plen > len)) {
                    qlen = (j - i + 1) / plen;

                    csol = 0;
                    for (k = j; k > j - plen; k--) {
                        memset(cnt, 0, sizeof(cnt));
                        vmax = 0;
                        for (l = 0; l < 4; l++) {
                            cnt[l] = c[l][k][plen] - c[l][max(k - (j - i + 1), 0)][plen];
                            if (cnt[l] > vmax)
                                vmax = cnt[l];
                        }

                        csol += (qlen - vmax);

                        if (csol >= sol[i][j])
                            break;
                    }

                    if (csol < sol[i][j])
                        sol[i][j] = csol;
                }
            }

            sol[j][i] = sol[i][j];
        }
    }
}

int main() {
    // Read the input data.
    freopen("perb.in", "r", stdin);
    scanf("%d %d", &N, &M);
    scanf("%s", s + 1);

    // Precompute.
    precompute();

    // Process the queries.
    freopen("perb.out", "w", stdout);
    while (M--) {
        scanf("%d %d", &i, &j);
        printf("%d\n", sol[i][j]);
    }

    return 0;
}