#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 1e5+5;
char s[M];
int sum[M][26];
int main(){
    int T,cas=1;
    scanf("%d",&T);
    while(T--){
        int n,q;
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        printf("Case #%d:\n",cas++);
        for(int j=1;j<=n;j++){
            for(int k=0;k<26;k++){
                sum[j][k]=sum[j-1][k];
            }
            sum[j][s[j]-'A']++;
        }
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            for(int j=0;j<26;j++){
                if(sum[r][j]-sum[l-1][j]){
                    printf("%d\n",sum[r][j]-sum[l-1][j]);
                    break;
                }
            }
        }
    }
    return 0;
}