#include <bits/stdc++.h>

using namespace std;

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(const string &s) {
  int n = s.size();
  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)
          dp[i][j] = min(dp[i][j], rez);
        }
      }
    }

  return dp;
}

int main() {
  ifstream cin("perb.in");
  ofstream cout("perb.out");
  int n, m;
  string s;
  cin >> n >> m >> s;
  auto raspunsuri = precalc(s);

  for (; m > 0; --m) {
    int x, y;
    cin >> x >> y;
    cout << raspunsuri[x - 1][y - 1] << '\n';
  }

  return 0;
}