#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
char A[100100];
int S[26][100100];
il vd work(int yyb){
    int n=gi(),q=gi();
    scanf("%s",A+1);
    memset(S,0,sizeof S);
    for(int i=1;i<=n;++i)++S[A[i]-'A'][i];
    for(int j=0;j<26;++j)
        for(int i=1;i<=n;++i)
            S[j][i]+=S[j][i-1];
    printf("Case #%d:\n",yyb);
    while(q--){
        int l=gi(),r=gi();
        for(int i=0;i<26;++i)
            if(S[i][r]-S[i][l-1]){
                printf("%d\n",S[i][r]-S[i][l-1]);
                break;
            }
    }
}
int main(){
    int T=gi();
    for(int i=1;i<=T;++i)work(i);
    return 0;
}