#include <bits/stdc++.h>
#define inf 999999999

using namespace std;

ifstream f("perb.in");
ofstream g("perb.out");

int n,q,x,y;
string s;
char c[]={'A','C','G','T'};
int minim[605][605];
int sum[6][605];


void init()
{
 for(int l=0;l<4;l++)
  for(int i=1;i<=n;i++)
   sum[l][i]=0;
}


int main()
{
f>>n>>q;
f>>s;
s=" "+s;

for(int i=1;i<=n;i++)
 for(int j=i;j<=n;j++)
  minim[i][j]=inf;

for(int pas=1;pas<=n;pas++)
 {
  minim[pas][pas]=0;
  init();

  for(int l=0;l<4;l++)
   for(int r=0;r<pas;r++)
   {
    if(r!=0) {if(s[r]==c[l]) sum[l][r]=1;}
    for(int i=r+pas;i<=n;i+=pas)
     {
      sum[l][i]=sum[l][i-pas];
      if(s[i]==c[l]) sum[l][i]++;
     }
   }

  for(int i=pas;i<=n;i++)
  {
   for(int j=i+pas;j<=n;j+=pas)
    {
     int salt=(j-i)/pas+1,tum=0;
     for(int z=j-pas+1;z<=j;z++)
      {
        if(z-salt*pas<=0) tum+=salt-max( max(sum[0][z],sum[1][z]) , max(sum[2][z],sum[3][z]) );
        else tum+=salt-max( max(sum[0][z]-sum[0][z-salt*pas],sum[1][z]-sum[1][z-salt*pas]) , max(sum[2][z]-sum[2][z-salt*pas],sum[3][z]-sum[3][z-salt*pas]) );
      }
     minim[i-pas+1][j]=min(minim[i-pas+1][j],tum);
    }
  }
 }

for(int i=1;i<=q;i++)
 f>>x>>y,g<<minim[x][y]<<'\n';
}