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

FILE *_fin;
int _in_loc; char _in_buff[4096];

void read_init(const char* nume) {
  _fin = fopen(nume, "r");
  _in_loc = 4095;
}

char read_ch() {
  ++_in_loc;
  if (_in_loc == 4096) {
    _in_loc = 0;
    fread(_in_buff, 1, 4096, _fin);
  }
  return _in_buff[_in_loc];
}

int read_u32() {
  int u32 = 0; char c;
  while (!isdigit(c = read_ch()) && c != '-');
  int sgn = 1;
  if (c == '-') {
    sgn = -1;
  } else {
    u32 = c - '0';
  }
  while (isdigit(c = read_ch())) {
    u32 = u32 * 10 + c - '0';
  }
  return u32 * sgn;
}

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() {
  read_init("perb.in");
  freopen("perb.out", "w", stdout);
  
  int N, M;
  N = read_u32();
  M = read_u32();
  char s[MAX_N + 5];
  for (int i = 1; i <= N; i++) {
    s[i] = read_ch();
  }
  for (int i = 0; i < M; i++) {
    x[i] = read_u32();
    y[i] = read_u32();
    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++) {
        memset(freq, 0, sizeof(freq));
        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++) {
    printf("%d\n", ans[x[i]][y[i]]);
  }
  return 0;
}