#include <bits/stdc++.h>

using namespace std;

int ap[26];

int solve(const string &s, int i, int j, int per, int v) {
  int sol = 0;

  for (int r = 0; r < per; ++r) {
    int best = 0, cnt = 0;

    for (int poz = i + r; poz <= j; poz += per) {
      ap[s[poz] - 'A']++;
      cnt++;

      if (ap[s[poz] - 'A'] > best) {
        best = ap[s[poz] - 'A'];
      }
    }

    sol += cnt - best;

    for (int poz = i + r; poz <= j; poz += per) {
      ap[s[poz] - 'A']--;
    }

    if (v <= sol) {
      return 666;
    }
  }

  return sol;
}

vector<vector<int>>precalc(const string &s) {
  int n = s.size();
  vector<vector<int>>dp(n, vector<int>(n, 666));

  for (int i = 0; i < n; ++i) {
    dp[i][i] = 1;
  }

  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j) {
      int lg = j - i + 1;

      for (int per = 1; per * per <= lg; ++per)
        if (lg % per == 0) {
          if (per != lg) {
            dp[i][j] = min(dp[i][j], solve(s, i, j, per, dp[i][j]));
          }

          if (lg / per != lg) {
            dp[i][j] = min(dp[i][j], solve(s, i, j, lg / per, dp[i][j]));
          }
        }
    }

  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;
}