#include <stdio.h>
#define nmax 602
long max, j, m, rez, i, poz, np, p, n, lg, ma[nmax][nmax], nr[nmax]['Z'], pan, inc, sf;
char c[5], s[nmax];

void calculare()
{
	rez=0;
	for (poz=1;poz<=p;poz++)
	{
		max=-1;
		for (j=1;j<=4;j++)
		{
			if (nr[sf-p+poz][c[j]]-nr[inc+poz-1][c[j]]+(s[inc+poz-1-1]==c[j])>max)
				max=nr[sf-p+poz][c[j]]-nr[inc+poz-1][c[j]]+(s[inc+poz-1-1]==c[j]);
		}
		rez+=np-max;
	}
	if (rez<ma[inc][sf])
		ma[inc][sf]=rez;
}

int main()
{
	freopen("perb.in","r",stdin);
	freopen("perb.out","w",stdout);
	c[1]='A';	c[2]='C';	c[3]='G';	c[4]='T';
	scanf("%ld %ld\n",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			ma[i][j]=nmax+1;
	gets(s);
	for (p=n/2;p>=1;p--)
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=4;j++)
			{
				pan=i-p;
				if (pan<0)
					pan=0;
				nr[i][c[j]]=nr[pan][c[j]]+(s[i-1]==c[j]);
			}
		for (inc=1;inc<=n;inc++)
			for (sf=inc;sf<=n;sf++)
				if (((sf-inc+1)%p==0) && ((sf-inc+1)>p))
				{
					lg=sf-inc+1;	np=lg/p;
					calculare();
				}
	}
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld",&inc,&sf);
		printf("%ld\n",ma[inc][sf]);
	}
	return 0;
}