#include <stdio.h>
#define MAXN 600
#define INF 2000000000
int d[MAXN][MAXN];
int nr[MAXN][4], 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;
  for(k = 1; k <= n; k++){
    for(i = 0; i + k - 1 < n; i++){
      sum = 0;
      for(j = 0; j < n; j++){
        max[j] = 0;
        for(l = 0; l < 4; l++){
          nr[j][l] = 0;
        }
      }
      for(j = i; j < n; j++){
        p = (j - i + 1) % k;
        nr[p][poz[s[j]]]++;
        if(nr[p][poz[s[j]]] > 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;
}