#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define pb push_back
#define sz size()
#define LL long long
#define SORT(x) sort(x.begin(), x.end())
#define REVERSE(x) reverse(x.begin(), x.end())
#define REP(x, hi) for (int x=0; x<(hi); x++)
#define FOR(x, lo, hi) for (int x=(lo); x<(hi); x++)
#define INFILE "perb.in" 
#define OUTFILE "perb.out"
#define MAX 612
ifstream fin (INFILE);
ofstream fout (OUTFILE);

char s[MAX];
int c[MAX][MAX], n;
int A[4][MAX][MAX];
char str[] = {'A', 'C', 'G', 'T'};


void comp_mat()
{
  memset(A, 0, sizeof(A));

  for(int k=0; k<4; k++)
    if( s[0]==str[k] )
      for(int i=0; i<n; i++)
        A[k][0][i] = 1;
  
  for(int i=1; i<n; i++)
  for(int j=1; j<n; j++)
  for(int k=0; k<4; k++)
  {
    A[k][i][j] = (s[i]==str[k]);
    if( i>=j ) A[k][i][j] += A[k][i-j][j];
  }

  /*for(int k=0; k<4; k++)
  {
    for(int j=0; j<n; j++)
    {
      for(int i=0; i<n; i++)
        cout << A[k][j][i] << " ";
      cout << endl;
    }
    cout << "\n\n";
  }*/
}

int getminchanges(int x, int y, int p)
{
  int changes = 0;
  for(int i=0; i<p; i++)
  {
    //int a,c,g,t; a = c = g = t = 0;
    /*for(int j = x+i; j<=y; j+=p )
      if( s[j]=='A' ) a++;
      else if( s[j]=='C' ) c++;
      else if( s[j]=='G' ) g++;
      else t++;*/

    int a[4] = {0};
    for(int k=0; k<4; k++)
      a[k] = A[k][y-p+1+i][p] - (x>p ? A[k][x+i-p][p] : 0);

    int maxf = max(max(a[0],a[1]), max(a[2],a[3]));
    changes += (y-x+1)/p - maxf;
  }
  return changes;
}

int getmin(int x, int y)
{
  int len = y-x+1;
  int minchanges = getminchanges(x, y, 1);
  for(int i=2; i*i<=len; i++)
    if( len%i==0 )
    {
      minchanges = min(minchanges, getminchanges(x, y, i));
      minchanges = min(minchanges, getminchanges(x, y, len/i));
    }
  return minchanges;
}

int main()
{
  int m;
  fin >> n >> m;
  REP(i, n)
  {
    fin >> s[i];
    c[i][i] = 0;
  }

  comp_mat();

  REP(i, n-1)
  for(int j=i+1;j<n; j++)
    c[i][j] = c[j][i] = getmin(i, j);

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