#include<cstdio>
const int M=1e5+5;
int T,n,q,cnt[M][27];
char str[M];
int main() {
    scanf("%d",&T);
    for(int kase=1; kase<=T; kase++) {
        scanf("%d%d",&n,&q);
        scanf("%s",str+1);
        for(int i=1;i<=n;i++)
            for(int j=0;j<26;j++)
                if(j==str[i]-'A')cnt[i][j]=cnt[i-1][j]+1;
                else cnt[i][j]=cnt[i-1][j];
        printf("Case #%d:\n",kase);
        for(int i=1;i<=q;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            for(int j=0;j<26;j++)
                if(cnt[r][j]-cnt[l-1][j]!=0){
                    printf("%d\n",cnt[r][j]-cnt[l-1][j]);
                    break;
                }
        }
    }
    return 0;
}