#include <stdio.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];

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

	for (i=1;i<=N;++i) {
		if (s[i]=='A') s[i]=0;
		else if (s[i]=='C') s[i]=1;
		else if (s[i]=='G') s[i]=2;
		else s[i]=3;
	}

	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)
		{
			b=1;
			for (j=0;j<d;++j) T[j][0]=T[j][1]=T[j][2]=T[j][3]=0,++T[j][s[i+j]];
			for (j=i+2*d-1;j<=N;j+=d){
				r=0;++b;
				for (k=0;k<d;++k) ++T[k][s[j-d+1+k]],r+=b-max(T[k][0],max(T[k][1],max(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;
}