#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[4][MAX][MAX], minchanges;
vector<vector<int> > d;

int getminchanges(int x, int y, int p)
{
   int changes = 0, len = (y-x+1)/p;
   for(int i=0; changes < minchanges && i<p; i++)
   {
      int maxf = 0;
      for(int j=0; j<4; j++)
           if(x+i>=p)  maxf = max(maxf, v[j][y-p+i+1][p] - v[j][x+i-p][p]);
           else   maxf = max(maxf, v[j][y-p+i+1][p]);
      changes += len - maxf;
   }
   return changes;
}

int getmin(int x, int y)
{
   int len = y-x+1;
   minchanges = MAX;
   if( d[len].size()==0 ) return getminchanges(x, y, 1);
   for(int k=0; k<d[len].size(); k++)
         minchanges = min(minchanges, getminchanges(x, y, d[len][k]));
   return minchanges;
}

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++)
      switch(buf[i])
      {
         case 'A': 
            s[i] = 0;
            break;
         case 'C':
            s[i] = 1;
            break;
         case 'G':
            s[i] = 2;
            break;
         default:
            s[i] = 3;
      }

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

   d.resize(n+1);
   for(int i=1; i<=n; i++)
   for(int j=i-1; j>1; j--)
      if( i%j==0 )
      {
         bool ok = 1;
         for(int k=0; ok && k<d[i].size(); k++)
            if( d[i][k]%j==0 ) ok = 0;
         if( ok ) d[i].push_back(j);
      }
   
   for(int i=0; i<n; i++)
   for(int p=1; p<=n/2; p++)
   for(int j=0; j<4; j++)
      if( i>=p )  v[j][i][p] = int(s[i]==j) + v[j][i-p][p];
      else v[j][i][p] = int(s[i]==j);
   
   //getmin(4, 9);
   for(int i=0; i<n; i++)
   for(int j=i+1;j<n; j++)
      c[i][j] = c[j][i] = getmin(i, j);

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