#include<fstream>

#define inf 20000000

using namespace std;

ifstream f("perb.in");

int best[1000][1000],nr[305][4],n,m;

char s[1000];

void preproc()
{
	int i,j,k,p,q,sum;
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			best[i][j]=inf;
	
	for (p=1;p<=n/2;++p)
		for (i=1;i<=n;++i)
		{
			memset(nr,0,sizeof(nr));
			q=-1;
			for (j=i;j<=n;++j)
			{
				++q;
				if (q==p)
					q=0;
				
				nr[q][s[j-1]-'A']++;
				
				if (j-i>=p && q==p-1)
				{
					sum=0;
					for (k=0;k<p;++k)
						sum+=(nr[k][0]+nr[k][1]+nr[k][2]+nr[k][3]-max(nr[k][0],max(nr[k][1],max(nr[k][2],nr[k][3]))));
					if (sum<best[i][j])
						best[i][j]=sum;
				}
			}
		}
}

void afisare()
{
	int i,x,y,j;
	char s1[30];
	ofstream g("perb.out");
	for (i=1;i<=m;i++)
	{
		s1[0]=0;
		f.get();
		f.get(s1,20);
		x=0,y=0;
		for (j=0;s1[j]!=' ';x=x*10+s1[j]-'0',++j);
		++j;
		for (;s1[j]!=0;y=y*10+s1[j]-'0',++j);
		
		g<<best[x][y]<<'\n';
	}
	f.close();
	g.close();
}

void citire()
{
	f>>n>>m;
	f>>s;
	for (int i=0;i<n;++i)
		if (s[i]=='C')
			s[i]='B';
		else
			if (s[i]=='G')
				s[i]='C';
			else
				if (s[i]=='T')
					s[i]='D';
}

int main()
{
	citire();
	preproc();
	afisare();
	return 0;
}