#include <bits/stdc++.h>
using namespace std;

const int maxn=100000+10;
const int INF=1e9;

int n,q;
char s[maxn];
int minv[5*maxn],sum[5*maxn][30];
int l,r;

void init(const int &v,const int &L,const int &R){
    minv[v]=min(minv[2*v],minv[2*v+1]);
    for(int i=0;i<26;i++)
        sum[v][i]=sum[2*v][i]+sum[2*v+1][i];
}
void build(const int &v,const int &L,const int &R){
    if(L==R){
        minv[v]=s[L]-'A';
        sum[v][minv[v]]=1;
        return;
    }
    int M=L+(R-L)/2;
    build(2*v,L,M);
    build(2*v+1,M+1,R);
    init(v,L,R);
}
int q_min(const int &v,const int &L,const int &R){
    if(l<=L&&r>=R)
        return minv[v];
    int M=L+(R-L)/2;
    int ml=INF,mr=INF;
    if(l<=M)
        ml=q_min(2*v,L,M);
    if(r>M)
        mr=q_min(2*v+1,M+1,R);
    return min(ml,mr);
}
int q_sum(const int &v,const int &L,const int &R,const int &tmp){
    if(l<=L&&r>=R){
        return sum[v][tmp];
    }
    int res=0;
    int M=L+(R-L)/2;
    if(l<=M)
        res+=q_sum(2*v,L,M,tmp);
    if(r>M)
        res+=q_sum(2*v+1,M+1,R,tmp);
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    int cnt=0;
    while(t--){
        printf("Case #%d:\n",++cnt);
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        memset(sum,0,sizeof(sum));
        build(1,1,n);
        for(int i=1;i<=q;i++){
            scanf("%d%d",&l,&r);
            int tmp=q_min(1,1,n);
            printf("%d\n",q_sum(1,1,n,tmp));
        }
    }
    return 0;
}