//Lambru Andrei Cristian - Algoritmiada 2011
//Runda Finala - clasele 5-9
#include<stdio.h>
#include<vector>

#define INF 1000000

short int A[610];
int B[5];
int N;
long int M;
char c;
int a;
int b;

int solve(int a,int b)
{
	int MIN = INF;
	int nr;
	int nr1;
	for(int i=1;i<=(b-a+1)/2;i++)
	{
		if((b-a+1)%i == 0)
		{
			nr1 = 0;
			for(int k=0;k<i;k++)
			{
				memset(B,0,sizeof(B));
				nr = -INF;
				for(int j=a+k;j<=b;j+=i)
					B[A[j]] ++;
				for(int l=1;l<=4;l++)
					if(nr<B[l])
						nr = B[l];
				nr1 += (b-a+1)/i-nr;
			}
			if(MIN>nr1)
				MIN = nr1;
		}
	}
	return MIN;
}

int main()
{
	FILE *f = fopen("perb.in","r");
	FILE *g = fopen("perb.out","w");
	
	fscanf(f,"%d %ld \n",&N,&M);
	for(int i=1;i<=N;i++)
	{
		fscanf(f,"%c",&c);
		if(c == 'A')
			A[i] = 1;
		else if(c == 'C')
			A[i] = 2;
		else if(c == 'G')
			A[i] = 3;
		else if(c == 'T')
			A[i] = 4;
	}
	for(int i=1;i<=M;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		fprintf(g,"%d\n",solve(a,b));
	}
	
	fclose(g);
	fclose(f);
	return 0;
}