#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define INFILE "perb.in" 
#define OUTFILE "perb.out"
#define MAX 612
ifstream fin (INFILE);
ofstream fout (OUTFILE);

int s[MAX], c[MAX][MAX], n, v[MAX][4];
string buf;

int main()
{
   int m;
   fin >> n >> m >> buf;

   for(int i=0; i<n; i++)
      if( buf[i]=='A' ) s[i] = 0;
      else if( buf[i]=='C' ) s[i] = 1;
      else if( buf[i]=='G' ) s[i] = 2;
      else if( buf[i]=='T' ) s[i] = 3;

   memset(c, 0x3f, sizeof(c));

   for(int i=0; i<n-1; i++)
   for(int p=1; i+2*p<n && p<=n/2; p++)
   {
      memset(v, 0, sizeof(v));
      for(int j=i, k=0; j<i+p; j++, k++)
         v[k][s[j]]++;

      for(int j=i+p, k=0, ps=2, changes=0; j<n; j++, k++)
      {
         v[k][s[j]]++;
         changes += ps - max(max(v[k][0], v[k][1]), max(v[k][2], v[k][3]));

         if( k==p-1 )
         {
            k = -1;    
            c[i][j] = min(c[i][j], changes);
            changes = 0;
            ps++;
         }
      }

   }

   for(int i=0; i<m; i++)
   {
      int x, y;
      fin >> x >> y;
      if( x>y ) swap(x, y);
      if( x==y )  fout << "0\n";
      else        fout << c[x-1][y-1] << endl;
   }
	
   return 0;
}