#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];

int main()
{
   int m;
   fin >> n >> m;
   char buf[1024];
   fin.getline(buf, 1024);
   fin.getline(buf, 1024);
   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; i++)
      c[i][i] = 0;

   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; j<i+p; j++)
         v[j-i][s[j]]++;

      for(int j=i+p, k=0; j<n; j++, k++)
      {
         v[k][s[j]]++;

         if( k==p-1 )
         {
            k = -1;
            int changes = 0;
            for(int l=0; l<p; l++)
            {
               changes += (j+1-i)/p - max(max(v[l][0], v[l][1]), max(v[l][2], v[l][3]));
            }
            c[i][j] = min(c[i][j], changes);
         }
      }

   }

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