#include <stdio.h>
#define MAXN 600
#define INF 2000000000
int d[MAXN][MAXN];
int nr[4][MAXN], max[MAXN], poz[256];
char s[MAXN + 2];

inline void precalc(int n){
  poz['A'] = 0;  poz['C'] = 1;  poz['T'] = 2;  poz['G'] = 3;
  int i, j, k, l, p, sum, cdr, cn = n / 2;
  for(k = 1; k <= cn; k++){
    cdr = n + 1 - k;
    for(i = 0; i < cdr; i++){
      sum = 0;
      for(j = 0; j < 4; j++)
        memset(nr[j], 0, sizeof nr[j]);
      memset(max, 0, sizeof max);
      p = 0;
      for(j = i; j < n; j++){
        p++;
        if(p == k)
          p -= k;
        nr[poz[s[j]]][p]++;
        if(nr[poz[s[j]]][p] > max[p]){
          sum++;
          max[p]++;
        }
        if(p == 0 && j - i + 1 != k && j - i + 1 - sum < d[i][j])
          d[i][j] = d[j][i] = j - i + 1 - sum;
      }
    }
  }
}

int main(){
  FILE *in = fopen("perb.in", "r");
  int n, m, i, j, x, y, aux;
  fscanf(in, "%d%d ", &n, &m);
  fgets(s, n + 2, in);
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      d[i][j] = INF;
  precalc(n);
  FILE *out = fopen("perb.out", "w");
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    x--;  y--;
    fprintf(out, "%d\n", d[x][y]);
  }
  fclose(in);
  fclose(out);
  return 0;
}