#include <cstdio>
#include <cstring>
using namespace std;

char a[100010];
int b[26][100010];
int T, TT, i, n, m, l, r, j;

int main() {
  scanf("%d", &T);
  for (int TT = 1; TT <= T; ++TT) {
    printf("Case #%d:\n", TT);
    scanf("%d%d", &n, &m);
    scanf("%s", a);
    memset(b, 0, sizeof(b));
    for (i = 1; i <= n; ++i) {
      b[a[i-1] - 'A'][i] = 1;
      for (j = 0; j < 26; ++j)
        b[j][i] += b[j][i-1];
    }

    while (m--) {
      scanf("%d%d", &l, &r);
      for (i = 0; i < 26; ++i) {
        if (b[i][r] - b[i][l-1] != 0) {
          printf("%d\n", b[i][r] - b[i][l-1]);
          break;
        }
      }
    }

  }
  return 0;
}