#include <fstream>

using namespace std;

const char InFile[]="perb.in";
const char OutFile[]="perb.out";
const int MaxN=666;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,Q,x,y,qmem[MaxN][MaxN],viz[MaxN][MaxN];
char str[MaxN];

inline int query(int x, int y)
{
	if(viz[MaxN][MaxN])
	{
		return qmem[x][y];
	}
	int N=y-x+1;
	int sol=MaxN;
	for(register int i=1;i<=(N>>1);++i)
	{
		if(N%i==0)
		{
			int best=0;
			for(register int j=x;j<=x+i-1;++j)
			{
				int A,C,T,G;
				A=C=T=G=0;
				int pos=j;
				while(pos<=y)
				{
					if(str[pos]=='A')
					{
						++A;
					}
					else if(str[pos]=='C')
					{
						++C;
					}
					else if(str[pos]=='T')
					{
						++T;
					}
					else if(str[pos]=='G')
					{
						++G;
					}
					pos+=i;
				}
				best+=A+C+T+G-max(max(A,C),max(T,G));
			}
			sol=min(sol,best);
		}
	}
	viz[x][y]=1;
	qmem[x][y]=sol;
	return sol;
}

int main()
{
	fin>>N>>Q>>(str+1);
	for(register int q=1;q<=Q;++q)
	{
		fin>>x>>y;
		fout<<query(x,y)<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}