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

const int maxn = 100100;
int n, q;
char s[maxn];
int f[27][maxn];

signed main() {
  // freopen("in", "r", stdin);
  int T, _ = 0;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%d",&n,&q);
    scanf("%s", s+1);
    memset(f, 0, sizeof(f));
    for(int i = 0; i < 26; i++) {
      for(int j = 1; j <= n; j++) {
        if('A'+i == s[j]) {
          f[i][j] = f[i][j-1] + 1;
        }
        else f[i][j] = f[i][j-1];
      }
    }
    int l, r;
    printf("Case #%d:\n", ++_);
    while(q--) {
      scanf("%d%d",&l,&r);
      int ret = 0;
      for(int i = 0; i < 26; i++) {
        if(f[i][r] - f[i][l-1]) {
          ret = f[i][r] - f[i][l-1];
          break;
        }
      }
      printf("%d\n", ret);
    }
  }
  return 0;
}