#include <bits/stdc++.h>
using namespace std;

ifstream fi("perb.in");
ofstream fo("perb.out");

const int N = 605;

int n, m;

int f[N][N][4], ans[N][N], mp[256], cnt[4];
char str[N];


static void init() {
	int tmp_ans, len;

	for (int pas = 1; pas <= n; ++pas)
		for (int pos = 0; pos < n; ++pos)
			for (int t = pos; t < n; t+= pas)
				f[pas][pos][mp[str[t]]]+= 1;

	memset(ans, 0x3f, sizeof ans);
	for (int i = 1; i <= n; ++i)
		ans[i][i] = 0;

	for (int pas = 1; pas <= n; ++pas)
	for (int st = 0; st < n; ++st) {
		for (int dr = st + pas + pas - 1; dr < n; dr+= pas) { // N^2 till here
			tmp_ans = 0;
			len = dr - st + 1;

			for (int i = 0; i < pas; ++i) { // aaand... another N
				memset(cnt, 0x00, sizeof cnt);
				for (int ch = 0; ch < 4; ++ch)
					cnt[ch] = f[pas][st + i][ch] - f[pas][min(n, st + i + len / pas * pas)][ch]; // !!!
				tmp_ans+= accumulate(cnt, cnt + 4, 0) - *max_element(cnt, cnt + 4); }

			ans[st][dr] = min(ans[st][dr], tmp_ans); } } }

int main() {
	fi >> n >> m;
	fi >> str;

	mp['A'] = 0, mp['G'] = 1, mp['T'] = 2, mp['C'] = 3;

	init();
	while (m--) {
		int l, r;
		fi >> l >> r;
		fo << ans[--l][--r] << '\n'; }

	return 0; }