#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("perb.in");
ofstream fout("perb.out");

const int INF = 0x3f3f3f3f;
int n, m, now[602][4];
int res[602][602];
char a[602];

inline int get(const char &a) {
	if (a == 'A') return 0;
	if (a == 'C') return 1;
	if (a == 'G') return 2;
	return 3;
}

inline int Max(int a, int b, int c, int d) {
	return max(max(a, b), max(c, d));
}

int main() {
	fin >> n >> m;
	fin >> (a + 1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			res[i][j] = INF;
		}
	}
	for (int start = 1; start <= n; ++start) {
		for (int len = 1; start + 2 * len - 1 <= n; ++len) {
			int re = 0, ind = 1;
			for (int i = start; i < start + len; ++i) {
				for (int j = 0; j < 4; ++j) {
					now[i - start + 1][j] = 0;
				}
			}
			for (int i = start; i < start + len; ++i) {
				++now[i - start + 1][get(a[i])];
			}
			for (int end = start + len; end <= n; ++end) {
				int mx = 0, sm = 0;
				++now[ind][get(a[end])];
				for (int i = 0; i < 4; ++i) {
					sm += now[ind][i];
					mx = max(mx, now[ind][i]);
				}
				++ind;
				re = re + sm - mx;
				if ( (end - start + 1) % len == 0 ) {
					res[start][end] = min(res[start][end], re);
					re = 0; ind = 1;
				}
			}
		}
	}
	for (int x, y, i = 1; i <= m; ++i) {
		fin >> x >> y;
		fout << res[x][y] << '\n';
	}
}