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

using namespace std;
const int maxn=100000+100;
const int INF=2147400000;
int T,n,q;
char s[maxn];
int minv[4*maxn],sumv[4*maxn][27];
void maintain(int o,int L,int R){
    minv[o]=min(minv[2*o],minv[2*o+1]);
    for(int i=0;i<26;i++)
        sumv[o][i]=sumv[2*o][i]+sumv[2*o+1][i];
}
void build(int o,int L,int R){
    if(L==R){
        minv[o]=s[L]-'A';
        sumv[o][s[L]-'A']=1;
        return;
    }
    int M=L+(R-L)/2;
    build(2*o,L,M);
    build(2*o+1,M+1,R);
    maintain(o,L,R);
}
int ql,qr;
int q_min(int o,int L,int R){
    if(ql<=L&&qr>=R)
        return minv[o];
    int M=L+(R-L)/2;
    int ml=INF,mr=INF;
    if(ql<=M)
        ml=q_min(2*o,L,M);
    if(qr>M)
        mr=q_min(2*o+1,M+1,R);
    return min(ml,mr);
}
int v;
int q_sum(int o,int L,int R){
    if(ql<=L&&qr>=R){
        return sumv[o][v];
    }
    int res=0;
    int M=L+(R-L)/2;
    if(ql<=M)
        res+=q_sum(2*o,L,M);
    if(qr>M)
        res+=q_sum(2*o+1,M+1,R);
    return res;
}
int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        printf("Case #%d:\n",t);
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        memset(sumv,0,sizeof(sumv));
        build(1,1,n);
        for(int i=1;i<=q;i++){
            scanf("%d%d",&ql,&qr);
            v=q_min(1,1,n);
            printf("%d\n",q_sum(1,1,n));
        }
    }
return 0;
}