#include <fstream>
#include <cstring>

using namespace std;

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

int n, q, a, y;

char s[605];
short f[605][5], mx[605], dp[605][605];
int x[30];

int main() {
  cin >> n >> q >> (s + 1);
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++)
      dp[i][j] = 1e9;
  }
  x['C' - 'A'] = 1; x['G' - 'A'] = 2; x['T' - 'A'] = 3;
  for(int l = 1; l <= n / 2; l++) {
    for(int i = 1; i <= n - l + 1; i++) {
      memset(f, 0, sizeof(f));
      memset(mx, 0, sizeof(mx));
      short cnt = 1, sum = 0;
      for(int j = i; j <= i + l - 1; j++) {
        int p = j - (cnt - 1) * l;
        f[p][x[s[j] - 'A']]++;
        mx[p] = max(mx[p], f[p][x[s[j] - 'A']]);
      }
      cnt++;
      for(int j = i + l; j <= n; j++) {
        int p = j - (cnt - 1) * l;
        f[p][x[s[j] - 'A']]++;
        mx[p] = max(mx[p], f[p][x[s[j] - 'A']]);
        sum += cnt - mx[p];
        if(j - i + 1 == cnt * l) {
          dp[i][j] = min(dp[i][j], sum);
          cnt++;
          sum = 0;
        }
      }
    }
  }
  for(; q; q--) {
    cin >> a >> y;
    if(a > y)
      swap(a, y);
    cout << dp[a][y] << "\n";
  }
  return 0;
}