#include <bits/stdc++.h>
using namespace std;

int sum[30][100010];
char str[100010];
int main() {
  int T;
  int iCase = 0;
  scanf("%d", &T);
  while (T--) {
    iCase++;
    int n,q;
    scanf("%d%d", &n, &q);
    scanf("%s", str);
    for (int i = 0; i < 26; i++)
      for (int j = 0; j <= n; j++)
        sum[i][j] = 0;
    for (int i = 0; i < n; i++) {
      sum[str[i]-'A'][i+1]++;
    }
    for (int i = 0; i < 26; i++)
      for (int j = 1; j <= n; j++)
        sum[i][j] += sum[i][j-1];
    int l,r;
    printf("Case #%d:\n", iCase);
    while (q--) {
      scanf("%d%d", &l, &r);
      for (int i = 0; i < 26; i++) {
        if (sum[i][r] - sum[i][l-1] > 0) {
          printf("%d\n", sum[i][r] - sum[i][l-1]);
          break;
        }
      }
    }
  }
  return 0;
}