#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
int sum[100100][26];
char gc(){
    char p=getchar();
    while(!isupper(p))p=getchar();
    return p;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int Id=1;Id<=T;Id++){
        printf("Case #%d:\n",Id);
        int n,q;
        scanf("%d%d",&n,&q);
        memset(sum[0],0,sizeof sum[0]);
        for(int i=1;i<=n;i++){
            memcpy(sum[i],sum[i-1],sizeof sum[0]);
            int x=gc()-'A';
            sum[i][x]++;
        }
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);l--;
            for(int j=0;j<26;j++){
                int v=sum[r][j]-sum[l][j];
                if(v){
                    printf("%d\n",v);
                    break;
                }
            }
        }
    }
    return 0;
}