#include <bits/stdc++.h>

using namespace std;

char s[502];
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[502][26], best[502], cnt[502];

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

  for (int j = 0; j <= per; ++j) {
    best[j] = 0;
    cnt[j] = 0;
  }
}

vector<vector<int>>precalc() {
  vector<vector<int>>dp(n, vector<int>(n));

  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 < 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;
          }
        }
      }
    }

  return dp;
}

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();
  }

  auto raspunsuri = precalc();

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

  return 0;
}