#include <bits/stdc++.h>

using namespace std;

const int NMAX = 610, AMAX = 100, inf = 0x3f3f3f3f;

int N, M;
int C[AMAX], DP[NMAX][NMAX], answer[NMAX][NMAX], cnt[NMAX / 2][5], added[NMAX], MOD[NMAX], max_index[NMAX];
char str[NMAX];

int main() {
	ios_base::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
	assert(freopen("perb.in", "r", stdin) != NULL);
    assert(freopen("perb.out", "w", stdout) != NULL);
    assert(freopen("debug.err", "w", stderr) != NULL);
    #endif

    C['A'] = 0;
    C['C'] = 1;
    C['G'] = 2;
    C['T'] = 3;

    int d, i, j, k;

    scanf("%d %d\n", &N, &M);
    scanf("%s", str + 1);

    for (i = 1; i <= N; ++i)
        str[i] = C[str[i]];

    memset(answer, inf, sizeof(answer));
    for (d = 1; d <= N / 2; ++d) {
        for (i = 1; i <= N; ++i) {
            MOD[i] = MOD[i - 1] + 1;
            if (MOD[i] >= d)
                MOD[i] -= d;
        }


        for (i = 1; i <= N; ++i) {
            memset(cnt, 0, sizeof(cnt));
            memset(added, 0, sizeof(added));
            memset(max_index, 0, sizeof(max_index));
            for (j = i; j <= N; ++j) {
                int index = MOD[j - i + 1];
                ++cnt[index][str[j]];
                ++cnt[index][4];

                if (cnt[index][str[j]] > cnt[index][max_index[index]])
                    max_index[index] = str[j];

                int add = cnt[index][4] - cnt[index][max_index[index]];

                DP[i][j] = DP[i][j - 1] - added[index] + add;
                added[index] = add;

                if (index == 0 && (j - i + 1) / d > 1)
                    answer[i][j] = min(answer[i][j], DP[i][j]);
            }
        }
    }

    char line[20];
    getchar();
    while (M--) {
        gets(line);
        i = 0, j = 0;
        for (k = 0; line[k] != ' '; ++k)
            i = i * 10 + line[k] - '0';
        for (++k; line[k]; ++k)
            j = j * 10 + line[k] - '0';
        //cout << answer[i][j] << '\n';
        printf("%d\n", answer[i][j]);
    }

	return 0;
}