#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>

const int MAX_N = 600;

int ans[5 + MAX_N][5 + MAX_N];
int freq[5 + MAX_N][4];

int code(char ch) {
  switch (ch) {
    case 'A':
      return 0;
      break;
    case 'C':
      return 1;
      break;
    case 'G':
      return 2;
      break;
  }
  return 3;
}

int main() {
  freopen("perb.in", "r", stdin);
  freopen("perb.out", "w", stdout);
  
  int N, M;
  scanf("%d%d\n", &N, &M);
  char s[MAX_N + 5];
  scanf("%s", s + 1);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      if (i != j) {
        ans[i][j] = INT_MAX;
      }
    }
  }
  for (int i = 1; i <= N; i++) {
    for (int d = 1; d <= N; d++) {
      memset(freq, 0, sizeof(freq));
      for (int j = i + d - 1; j <= N; j += d) {
        int sol = 0;
        for (int k = j - d + 1; k <= j; k++) {
          freq[k % d][code(s[k])]++;
          sol += (j - i + 1) / d - std::max(freq[k % d][0], std::max(freq[k % d][1], std::max(freq[k % d][2], freq[k % d][3])));
        }
        if (j - i + 1 > d)
          ans[i][j] = std::min(ans[i][j], sol);
      }
    }
  }
  for (int i = 0; i < M; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", ans[x][y]);
  }
  return 0;
}