#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <numeric>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2000000000
#define NMAX 605
#define NRCHARS 4

char s[NMAX];
int nr[NMAX][NRCHARS];
int best[NMAX][NMAX];
int h[256];

void precalc(int);

int main()
{
	int i, n, m;
	ifstream fin("perb.in");
	ofstream fout("perb.out");

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

	(fin >> n >> m).ignore();
	fin.getline(s, NMAX);

	precalc(n);

	for (i = 1; i <= m; ++i)
	{
		int a, b;
		fin >> a >> b; --a; --b;

		fout << best[a][b] << '\n';
	}

	fin.close();
	fout.close();

	return 0;
}

void precalc(int n)
{
	int d, i, lg, j, sum, maxEl, changes;

	for (i = 0; i < n; ++i)
		for (j = i; j < n; ++j)
			best[i][j] = INF;

	for (d = 1; d <= n / 2; ++d)
		for (i = 0; i + 2 * d <= n; ++i)
		{
			memset(nr, 0, sizeof(nr));
			for (j = i; j < i + d; ++j) ++nr[j % d][h[s[j]]];

			for (lg = 2; i + lg * d <= n; ++lg)
			{
				for (j = i + (lg - 1) * d; j < i + lg * d; ++j) ++nr[j % d][h[s[j]]];

				for (changes = 0, j = 0; j < d; ++j)
				{
					sum = accumulate(nr[j], nr[j] + NRCHARS, 0);
					maxEl = *max_element(nr[j], nr[j] + NRCHARS);
					changes += sum - maxEl;
				}

				best[i][i + lg * d - 1] = min(best[i][i + lg * d - 1], changes);
			}
		}
}