#include<cstdio>
#include<algorithm>
#define infile "perb.in"
#define outfile "perb.out"
#define nMax 613

using namespace std;

short int ap[4][nMax][nMax];
short int dp[nMax][nMax];
short int w[nMax];
char v[nMax];
int n, m;

void read() {
  scanf("%d %d\n", &n, &m);
  scanf("%s\n", v+1);
}

void init() {

  for(int i = 1; i <= n; ++i)
    switch(v[i]) {
      case 'A' : w[i] = 0; break;
      case 'C' : w[i] = 1; break;
      case 'G' : w[i] = 2; break;
      case 'T' : w[i] = 3; break;
    }

  for(int k = 0; k < 4; ++k)
    for(int i = n; i > 0; --i) {
      for(int j = 1; j <= n; ++j) {
        if(w[i] == k) ap[k][i][j] = 1;
        if(i+j <= n) ap[k][i][j] += ap[k][i+j][j];
        //printf("ap(%d, %d, %d) = %d\n", k, i, j, ap[k][i][j]);
      }
    }
}

short int compute(int i, int j, int k, int best) {
  //printf("compute(%d, %d, %d) \n ", i, j, k);
  int len = j - i + 1;
  int cost = 0;
  int le, ri;
  int maxAp;

  if(k == len) return len;

  for(int it = 0; it < k && cost < best; ++it) {
    le = it + i;
    ri = min(n+1,  le + len);
    maxAp = max(max(ap[0][le][k]-ap[0][ri][k], ap[1][le][k]-ap[1][ri][k]), max(ap[2][le][k]-ap[2][ri][k], ap[3][le][k]-ap[3][ri][k]));
    cost += (len / k - maxAp);
    
    //for(type = 0; type < 4; ++type)
      //maxAp = max(maxAp, ap[type][le][k] - ap[type][ri][k]);
    //printf("(%d %d) = %d :: %d\n", le, ri, maxAp, len/k - maxAp);
  }

  //printf(" = %d\n", cost);
  return cost;
}

void solve() {

  for(int i = 1; i <= n; ++i)
    for(int j = i+1; j <= n; ++j) {
      int len = j - i + 1;
      dp[i][j] = len;
      for(int k = 1; k * k <= len; ++k)
        if(len % k == 0)
          dp[i][j] = min(dp[i][j], min(compute(i, j, k, dp[i][j]), compute(i, j, len/k, dp[i][j])));
    }

  int x, y;
  for(int i = 1; i <= m; ++i) {
    scanf("%d %d\n", &x, &y);
    printf("%d\n", dp[x][y]);
  }
}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  read();
  init();
  solve();

  fclose(stdin);
  fclose(stdout);
  return 0;
}