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

using namespace std;

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

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

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

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

	return 3;
}

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

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

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

void cit(int &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);
	int N, M; scanf("%d%d", &N, &M);

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

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

	for (int i = 0; i < N; ++i)
		for (int j = 1; j < N; ++j) {
			if (i + 2 * j > N)
				break;

			vector< vector<int> > apparitions(j, vector<int>(4, 0));
			vector<int> most(j, 0);

			int pas = 0;
			for (int k = i; k + j <= N; k += j) {
				int answer = 0;
				++pas;

				for (int p = 0; p < j; ++p) {
					int castcharacter = cast(S[k + p]);
					most[p] = max(most[p], ++apparitions[p][castcharacter]);
					answer += pas - most[p];
				}

				if (k != i)
					dp[i][k + j - 1] = min(dp[i][k + j - 1], answer);
			}
		}

	for (int i = 0; i < M; ++i) {
		int x, y; cit(x); cit(y);
		printf("%d\n", dp[x - 1][y - 1]);
	}
}