#include <stdio.h>
#include <string.h>
#define max(a,b) (a>b?a:b)

char adn[600];
int n,sol;
long m;

inline void cit(FILE *f)
{
	fscanf(f,"%i%li",&n,&m);
	fscanf(f,"%s",adn);
}

int nr(int s1,int s2,int pa)
{
	int i,sol=0;
	for(i=0;i<pa;i++)
		if(adn[s1+i]!=adn[s2+i])
			sol++;
	return sol;
}

int nr0(int a,int b)
{
	int i,A=0,C=0,T=0,G=0;
	for(i=a-1;i<b;i++)
		switch(adn[i])
		{
		case 'A':
			A++;
			break;
		case 'C':
			C++;
			break;
		case 'G':
			G++;
			break;
		case 'T':
			T++;
			break;
		}
	return b-a+1-max(A,max(C,max(G,T)));
}

void rez(int a,int b)
{
	int i,j,sum=0,sumMax=0xFFFF;
	for(i=1;i<=(b-a+1)/2;i++)
		if((b-a+1)%i==0)
		{
			if(i==1)
				sum=nr0(a,b);
			else
			{
				sum=0;
				for(j=a-1+i;j<b;j+=i)
					if(strncmp(adn+a-1,adn+j,i)!=0)
						sum+=nr(a-1,j,i);
			}
			if(sum<sumMax)
				sumMax=sum;
		}
	sol=sumMax;
}

int main()
{
	FILE *fi=fopen("perb.in","r"),*fo=fopen("perb.out","w");
	int a,b;
	long i;
	cit(fi);
	for(i=0;i<m;i++)
	{
		fscanf(fi,"%i%i",&a,&b);
		rez(a,b);
		fprintf(fo,"%i\n",sol);
		fflush(fo);
	}
	return 0;
}