#include <bits/stdc++.h>

using namespace std;

FILE *fin = fopen ("perb.in", "r"), *fout = fopen ("perb.out", "w");

const int INF = 1e9, MAXN = 600, DELTA = 4;

map <char, int> mp;

int sol[MAXN + 1][MAXN + 1], v[MAXN + 1][DELTA], a[MAXN + 1];
char s[MAXN + 1];

inline int solve (int st, int dr) {
  int mn, sl, d, s, mx, i, j;
  mn = INF;
  for (d = 1; d <= max (1, dr - st); d++) {
    if ((dr - st + 1) % d == 0) {
      sl = 0;
      for (i = 0; i < d; i++)
        for (j = 0; j < 4; j++)
          v[i][j] = 0;
      for (i = st; i <= dr; i++)
        v[(i - st) % d][a[i]]++;
      for (i = 0; i < d; i++) {
        int sum = 0;
        mx = 0;
        for (j = 0; j < 4; j++) {
          sum = sum + v[i][j];
          mx = max (mx, v[i][j]);
          v[i][j] = 0;
        }
        sl = sl + (sum - mx);
      }
      mn = min (mn, sl);
    }
  }
  return mn;
}

int main() {
  int n, m, i, st, dr;
  fscanf (fin, "%d%d", &n, &m);
  fscanf (fin, "%s", &s);
  mp['A'] = 0; mp['C'] = 1; mp['G'] = 2; mp['T'] = 3;
  for (i = 0; i < n; i++) {
    a[i + 1] = mp[s[i]];
  }
  for (st = 1; st <= n; st++)
    for (dr = st; dr <= n; dr++) {
      sol[st][dr] = solve (st, dr);
    }
  while (m--) {
    fscanf (fin, "%d%d", &st, &dr);
    fprintf (fout, "%d\n", sol[st][dr]);
  }
  fclose (fin);
  fclose (fout);
  return 0;
}