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

#define MAX 610
#define pb push_back

using namespace std;

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

inline int min(int x, int y)
{
	if (x < y)
		return x;
	return y;
}

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 = p + 1; i <= n + p; i++)
		{
			for (int k = 1; k <= 4; k++)
				ap[i][p][k] = ap[i - p][p][k];

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

	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			cost[i][j] = n;

	for (int st = 1; st <= n; st++)
		for (int div = 1; div <= n / 2 + 1; div++)
		{
			for (int ul = st + div; ul <= n + 1; ul += div)
			{
				int c = ul - st + div;
				for (int p = 0; p < div; p++)
					c -= max(max(ap[ul + div + p][div][1] - ap[st + p][div][1], ap[ul + div + p][div][2] - ap[st + p][div][2]), max(ap[ul + div + p][div][3] - ap[st + p][div][3], ap[ul + div + p][div][4] - ap[st + p][div][4]));
				cost[st][ul + div - 1] = min(cost[st][ul + div - 1], c);
			}
		}

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

		printf("%d\n", cost[x][y]);
	}

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