#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 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 maxf = max(max(a,c), max(g,t));
    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;
  }

  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;
}