#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 610
using namespace std;

const char IN[]="perb.in",OUT[]="perb.out";

int N,M;
int T[NMax][4];
int D[NMax][NMax];
char s[NMax];

void update(int *T,int poz){

	if (s[poz]=='A') ++T[1],++T[2],++T[3];
	if (s[poz]=='C') ++T[0],++T[2],++T[3];
	if (s[poz]=='G') ++T[0],++T[1],++T[3];
	if (s[poz]=='T') ++T[0],++T[1],++T[2];

}

int main()
{
	int i,j,k,d,r,x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d%s",&N,&M,s+1);

	for (i=1;i<=N;++i) for (j=i+1;j<=N;++j) D[i][j]=j-i+1;

	for (i=1;i<=N;++i)
	{
		for (d=1;i+2*d-1<=N;++d)
		{
			for (j=0;j<d;++j) T[j][0]=T[j][1]=T[j][2]=T[j][3]=0,update(T[j],i+j);
			for (j=i+2*d-1;j<=N;j+=d){
				r=0;
				for (k=0;k<d;++k) update(T[k],j-d+1+k);
				for (k=0;k<d;++k) r+=min(T[k][0],min(T[k][1],min(T[k][2],T[k][3])));
				D[i][j]=min(r,D[i][j]);
			}
		}
	}

	freopen(OUT,"w",stdout);
	while (M--){
		scanf("%d%d",&x,&y);
		printf("%d\n",D[x][y]);
	}
	fclose(stdout);
	return 0;
}