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

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

const int MAX_N = 600;
const int MAX_M = 500000;

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 x[MAX_M];
int y[MAX_M];
int maxVizX[1 + MAX_N];

int main() {
  int N, M;
  cin >> N >> M;
  char s[MAX_N + 5];
  cin >> (s + 1);
  for (int i = 0; i < M; i++) {
    cin >> x[i] >> y[i];
    maxVizX[x[i]] = std::max(maxVizX[x[i]], y[i]);
  }
  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++) {
    if (maxVizX[i] > 0) {
      for (int d = 1; d <= (N - i + 1) / 2; d++) {
        for (int j = 0; j < d; j++) {
          freq[j][0] = freq[j][1] = freq[j][2] = freq[j][3] = 0;
        }
        for (int j = i + d - 1; j <= maxVizX[i]; 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++) {
    cout << ans[x[i]][y[i]] << '\n';
  }
  return 0;
}