#include <bits/stdc++.h>

using namespace std;

ifstream fin ("perb.in");
ofstream fout ("perb.out");

int n, m, dp[602][602], f[602][26], aux, t, Max[602];
int x, y;
char s[602];

int main()
{
  fin >> n >> m;
  fin >> (s + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      dp[i][j] = (int)1e6;
  for (int d = 1; d <= n / 2; d++)
    for (int i = 1; i <= n - d + 1; i++) {
      t = 1;
      aux = 0;
      memset(Max, 0, sizeof(Max));
      memset(f, 0, sizeof(f));
      for (int j = i; j <= n; j++) {
        int rest = j - (t - 1) * d;
        f[s[j] - 'A'][rest]++;
        Max[rest] = max(Max[rest], f[s[j] - 'A'][rest]);
        aux += t  - Max[rest];
        if ((j - i + 1) == t * d) {
          if (j - i + 1 > d)
            dp[i][j] = min(dp[i][j], aux);
          t++;
          aux = 0;
        }
      }
    }
  while (m--) {
    fin >> x >> y;
    fout << dp[x][y] << "\n";
  }
  return 0;
}