#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[MAX][4];
int cost[MAX][MAX];
char strCit[2 * MAX];

inline int max(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['A'] = 0;
	norm['C'] = 1;
	norm['G'] = 2;
	norm['T'] = 3;
	for (int i = 1; i <= n; i++)
		strCit[i] = norm[strCit[i]];

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

			for (int p = 0; p < div; p++)
				ap[p][strCit[st + p]]++;

			for (int ul = st + div; ul + div <= n + 1; ul += div)
			{
				int c = ul - st + div;
				for (int p = 0; p < div; p++)
				{
					ap[p][strCit[ul + p]]++;

					int sc = 0;
					for (int k = 0; k < 4; k++)
						sc = max(sc, ap[p][k]);

					c -= sc;
				}
				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;
}