#include <cstdio>
#include <cstring>
#include <cstdlib>

#define nmax 612

int *A[nmax][nmax], n, m, count[256];
char s[nmax];

int test(int a, int b, int l)
{
  int idx = (b - a + 1) / l - 1;
  int tmp = A[a + l - 1][l][idx];
  if(a)
    tmp -= A[a - 1][l][idx];
  return tmp;
}

int doit(int a, int b)
{
  int i, res = test(a, b, 1), l = b - a + 1, tmp;
  for(i = 2; i * i <= l; ++i)
  {
    if(l % i)
      continue;
    tmp = test(a, b, i);
    if(tmp < res)
      res = tmp;
    tmp = test(a, b, l / i);
    if(tmp < res)
      res = tmp;
  }
  return res;
}

int main()
{
  int i, j, l, mx, idx, a, b;
  freopen("perb.in", "r", stdin);
  freopen("perb.out", "w", stdout);
  scanf("%d %d", &n, &m);
  scanf("%s", s);
  for(i = 0; i < n; ++i)
    for(j = 1; j <= n; ++j)
    {
      memset(count, 0, sizeof(count));
      A[i][j] = (int *)malloc((nmax / j) * sizeof(int));
      for(mx = 0, idx = 0, l = i; l < n; l +=j, idx++)
      {
        count[s[l]]++;
        if(mx < count[s[l]])
          mx = count[s[l]];
        A[i][j][idx] = idx + 1 - mx;
        if(i)
          A[i][j][idx] += A[i - 1][j][idx];
      }
    }
  for(i = 0; i < m; ++i)
  {
    scanf("%d %d", &a, &b);
    --a, --b;
    printf("%d\n", doit(a, b));
  }
  return 0;
}