#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][4], added[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;

    cin >> N >> M;
    cin >> (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) {
            memset(cnt, 0, sizeof(cnt));
            memset(added, 0, sizeof(added));
            for (j = i; j <= N; ++j) {
                int index = (j - i + 1) % d;
                ++cnt[index][str[j]];

                int max_index = 0;
                for (k = 1; k < 4; ++k)
                    if (cnt[index][k] > cnt[index][max_index])
                        max_index = k;

                int add = 0;
                for (k = 0; k < 4; ++k)
                    if (max_index != k)
                        add += cnt[index][k];

                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]);
            }
        }
    }

    while (M--) {
        cin >> i >> j;
        cout << answer[i][j] << '\n';
    }

	return 0;
}