#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

ifstream f(iname);
ofstream g(oname);

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

int main() {
	int N, M; f >> N >> M;
	string S; f >> 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; f >> x >> y;
		g << dp[x - 1][y - 1] << "\n";
	}
}