#include <algorithm>
#include <climits>
#include <cstring>
#include <fstream>

std::ifstream cin("perb.in");
std::ofstream cout("perb.out");

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() {
  int N, M;
  cin >> N >> M;
  char s[MAX_N + 5];
  cin >> (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;
    cin >> x >> y;
    cout << ans[x][y] << '\n';
  }
  return 0;
}