#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, d, pr[nmax];
char c[5], s[nmax];

void ciur()
{
	pr[1]=1;d=2;
	while (d*d<=nmax)
	{
		if (!pr[d])
			for (j=2;j*d<=nmax;j++)
				pr[j*d]=1;
		if (d==2)
			d++;
		else
			d+=2;
	}
}

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);
	ciur;
	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 (lg=1;lg<=n;lg++)
			if (!pr[(sf-inc+1)/p])
				for (inc=1;inc<=n;inc++)
				{
					sf=inc+lg-1;
					if (((sf-inc+1)%p==0) && ((sf-inc+1)>p))
					{	
						np=lg/p;
						calculare();
					}
				}
	}
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld",&inc,&sf);
		if (inc==sf)
			printf("1\n");
		else
			printf("%ld\n",ma[inc][sf]);
	}
	return 0;
}