#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const char iname[] = "perb.in";
const char oname[] = "perb.out";
const size_t buffer = 4096;

inline size_t cast(const char &x) {
	if (x == 'A')
		return 0;

	if (x == 'C')
		return 1;

	if (x == 'G')
		return 2;

	return 3;
}

inline size_t max(const size_t &A, const size_t &B) {
	if (A < B)
		return B;
	return A;
}

inline size_t min(const size_t &A, const size_t &B) {
	if (A < B)
		return A;
	return B;
}

char s[buffer];
size_t p = buffer - 1;

void cit(size_t &x) {
	x = 0;
	while (s[p] < '0' || s[p] > '9')
		if (++p == buffer)
			fread(s, 1, buffer, stdin), p = 0;

	while (s[p] >= '0' && s[p] <= '9') {
		x = x * 10 + s[p] - '0';
		if (++p == buffer)
			fread(s, 1, buffer, stdin), p = 0;
	}
}

int main() {
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	size_t N, M; scanf("%u%u", &N, &M);

	char S[650];
	memset(S, 0, sizeof(S)); scanf("%s", S);

	vector< vector<size_t> > dp(N, vector<size_t>(N));
	for (size_t i = 0; i < N; ++i)
		for (size_t j = i + 1; j < N; ++j)
			dp[i][j] = j - i;

	for (size_t period = 1; period <= N / 2; ++period) {
		vector< vector<size_t> > apparitions(N, vector<size_t>(4, 0));

		for (size_t i = 0; i < N; ++i)
			for (size_t j = 0; j < 4; ++j)
				apparitions[i][j] = static_cast<int>(cast(S[i]) == j) + (i >= period ? apparitions[i - period][j] : 0);

		for (size_t repeat = 2; repeat * period <= N; ++repeat) {
			vector<size_t> substitutions(N - (repeat - 1) * period, 0);

			size_t sum = 0;
			for (size_t i = (repeat - 1) * period; i < N; ++i) {

				size_t aux(0);
				for (size_t j = 0; j < 4; ++j)
					aux = max(aux, apparitions[i][j] - (i >= repeat * period ? apparitions[i - repeat * period][j] : 0));

				substitutions[i - (repeat - 1) * period] = repeat - aux;

				sum += substitutions[i - (repeat - 1) * period];
				if (i >= repeat * period)
					sum -= substitutions[i - repeat * period];

				if (i >= repeat * period - 1)
					dp[i - repeat * period + 1][i] = min(dp[i - repeat * period + 1][i], sum);
			}
		}
	}

	for (size_t i = 0; i < M; ++i) {
		size_t x, y;
		cit(x); cit(y);

		printf("%d\n", dp[x - 1][y - 1]);
	}
}