#include <bits/stdc++.h>
using namespace std;
int c, T, n, q, ans[100005];
char s[100005];
bitset<50005>dp[2], f[2][30], g[2][30], F[50005], kk;
struct st {
  int a, b;
  st() {}
  st (int A, int B) {
    a = A, b = B;
  }
};
vector<st> v[100005];
int main() {
  scanf ("%d%d", &c, &T);
  for (int i = 1; i <= 50000; i++) F[i] = F[i - 1], F[i][i] = 1;
  while (T--) {
    scanf ("%d%d", &n, &q);
    scanf ("%s", s + 1);
    for (int i = 'a'; i <= 'z'; i++) {
      f[0][i - 'a'] = f[1][i - 'a'] = kk;
      for (int j = 1; j <= n / 2; j++) {
        f[0][i - 'a'][j] = i < s[j * 2];
        if (j * 2 + 1 <= n) f[1][i - 'a'][j] = i < s[j * 2 + 1];
        g[0][i - 'a'][j] = i <= s[j * 2];
        if (j * 2 + 1 <= n) g[1][i - 'a'][j] = i <= s[j * 2 + 1];
      }
    }
    dp[0] = dp[1] = kk;
    int kkk = 0;
    for (int i = 1, a, b; i <= q; i++) scanf ("%d%d", &a, &b), v[a].push_back (st (b, i) ), kkk = min (kkk, a);
    for (int i = n; i >= kkk; i--) {
      dp[i & 1] = ( ( ( (dp[ (i & 1) ^ 1] << ( (i + 1) / 2) ) | f[ (i & 1) ^ 1][s[i] - 'a']) &g[ (i & 1) ^ 1][s[i] - 'a']) ) >> ( (i - 1) / 2);
      for (int j = 0; j < v[i].size(); j++) ans[v[i][j].b] = (dp[i & 1] & F[v[i][j].a]).count();
      v[i].clear();
    }
    for (int i = 1; i <= q; i++) printf ("%d\n", ans[i]);
  }
}