#include <stdio.h>
#define NMax 605
#define MMax 500005
#define INF 2000000000
FILE *fin = fopen("perb.in", "rt");
FILE *fout = fopen("perb.out", "wt");

int n, m;
char s[NMax];

int st[MMax], en[MMax];
int ap[NMax][NMax / 2][4];

int nr[256];

int main()
{
	nr['A'] = 0;
	nr['C'] = 1;
	nr['G'] = 2;
	nr['T'] = 3;

	fscanf(fin, "%d %d\n", &n, &m);
	fscanf(fin, "%s", s);

	for (int i = 0; i < m; i++)
	{
		fscanf(fin, "%d %d", &st[i], &en[i]);
		st[i]--;
		en[i]--;
	}

	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 1; j <= n / 2; j++)
		{
			if (i + j >= n)
				ap[i][j][nr[s[i]]] = 1;
			else
			{
				for (int ch = 0; ch < 4; ch++)
					ap[i][j][ch] = ap[i+j][j][ch] + (ch == nr[s[i]]);
			}
		}
	}

	int l, nr, modmin, mod, ch, chmax, aptmp;
	for (int i = 0; i < m; i++)
	{
		modmin = INF;
		for (l = 1; l < en[i] - st[i] + 1; l++) if ((en[i] - st[i] + 1) % l == 0)
		{
			mod = 0;
			nr = (en[i] - st[i] + 1) / l;

			for (int j = 0; j < l; j++)
			{
				chmax = -1;
				for (ch = 0; ch < 4; ch++)
				{
					aptmp = ap[st[i] + j][l][ch];
					if (st[i] + j + en[i] - st[i] + 1 < n)
						aptmp -= ap[st[i] + j + en[i] - st[i] + 1][l][ch];
					if (chmax < aptmp)
						chmax = aptmp;
				}
				mod += nr - chmax;
			}

			if (modmin > mod)
				modmin = mod;
		}

		fprintf(fout, "%d\n", modmin);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}