#include <algorithm>
#include <stdio.h>
#include <map>
#include <vector>

#define MAX 610
#define pb push_back

using namespace std;

map <char, int> norm;
vector <int> vctDiv[MAX];
int n, q;
int ap[2 * MAX][MAX][5];
char strCit[2 * MAX];

int main()
{
	freopen("perb.in", "r", stdin);
	freopen("perb.out", "w", stdout);

	scanf("%d %d\n", &n, &q);

	fgets(strCit + 1, MAX, stdin);

	norm[0] = 0;
	norm['A'] = 1;
	norm['C'] = 2;
	norm['G'] = 3;
	norm['T'] = 4;
	for (int p = 1; p <= n; p++)
		for (int i = 1; i <= n + p; i++)
		{
			memcpy(ap[i][p], ap[i - p][p], sizeof(ap[i][p]));

			ap[i][p][norm[strCit[i - p]]]++;
		}

	for (; ; );

	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			if (i % j == 0)
				vctDiv[i].pb(j);

	for (; q; q--)
	{
		int x, y;
		scanf("%d %d", &x, &y);

		int l = y - x + 1, rez = n;
		for (int i = 0; i < vctDiv[l].size(); i++)
		{
			int div = vctDiv[l][i];

			int d = l / div, sum = 0;
			for (int s = x; s < x + div; s++)
				sum += d - max(max(ap[s + l][div][1] - ap[s][div][1], ap[s + l][div][2] - ap[s][div][2]), max(ap[s + l][div][3] - ap[s][div][3], ap[s + l][div][4] - ap[s][div][4]));
			rez = min(rez, sum);
		}

		printf("%d\n", rez);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}