#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int cnt[100005][26];
char str[100005];

int main() {
  int cases;
  scanf("%d",&cases);
  for(int t=1;t<=cases;t++) {
      int n,m;
      scanf("%d%d",&n,&m);
      scanf("%s",str+1);
      for(int i=1;i<=n;i++) {
          memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));
          cnt[i][str[i]-'A']++;
      }
    printf("Case #%d:\n",t);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        for(int j=0;j<26;j++)
          if (cnt[y][j]>cnt[x-1][j]) {
              printf("%d\n",cnt[y][j]-cnt[x-1][j]);
              break;
          }
    }
  }
  return 0;
}