#include <fstream>
#include <cstring>

using namespace std;

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

int n, q, x, y;

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

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;
  }
  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));
      int cnt = 1, sum = 0;
      for(int j = i; j <= i + l - 1; j++) {
        int p = j - (cnt - 1) * l;
        f[p][(s[j] - 'A')]++;
        mx[p] = max(mx[p], f[p][(s[j] - 'A')]);
      }
      cnt++;
      for(int j = i + l; j <= n; j++) {
        int p = j - (cnt - 1) * l;
        f[p][(s[j] - 'A')]++;
        mx[p] = max(mx[p], f[p][(s[j] - 'A')]);
        sum += cnt - mx[p];
        if(j - i + 1 == cnt * l && j >= i + l) {
          dp[i][j] = min(dp[i][j], sum);
          cnt++;
          sum = 0;
        }
      }
    }
  }
  for(; q; q--) {
    cin >> x >> y;
    if(x > y)
      swap(x, y);
    cout << dp[x][y] << "\n";
  }
  return 0;
}