#include <bits/stdc++.h>

using namespace std;

char s[602];
int n, m;

void Read(int &x) {
  x = 0;
  char c = getchar();

  while (!isdigit(c)) {
    c = getchar();
  }

  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
}
set<char>S = { 'A', 'C', 'G', 'T'};

int ap[603][26], best[603], cnt[603], dp[603][603];

inline void clear_(int per) {
  for (int j = 0; j <= per; ++j)
    for (auto i : S) {
      ap[j][i - 'A'] = 0;
    }

  memset(best, 0, sizeof(int) * (per + 1));
  memset(cnt, 0, sizeof(int) * (per + 1));
}

void precalc() {
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      dp[i][j] = j - i + 1;
    }
  }

  for (int per = 1; per <= n >> 1; ++per)
    for (int i = 0; i + 2 * per - 1 < n; ++i) {
      clear_(per);
      int r = 0, done = 0, rez = 0;

      for (int j = i; j < n; ++j) {
        r++;
        ap[r][s[j] - 'A'] ++;
        rez = rez - (cnt[r] - best[r]);

        if (ap[r][s[j] - 'A'] > best[r]) {
          best[r] = ap[r][s[j] - 'A'];
        }

        cnt[r]++;
        rez += (cnt[r] - best[r]);

        if (r == per) {
          r = 0;
          ++done;

          if (done != 1 && rez < dp[i][j]) {
            dp[i][j] = rez;
          }
        }
      }
    }
}

int main() {
  freopen("perb.in", "r", stdin);
  freopen("perb.out", "w", stdout);
  Read(n);
  Read(m);

  for (int i = 0; i < n; ++i) {
    s[i] = getchar();
  }

  precalc();

  for (; m > 0; --m) {
    int x, y;
    Read(x);
    Read(y);
    printf("%d\n", dp[x - 1][y - 1]);
  }

  return 0;
}