#include<bits/stdc++.h>
#define RAN(v)v.begin(),v.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
template<class T1,class T2>
inline void upd1(T1&a,const T2&b){
    if(a>b)a=b;
}
template<class T1,class T2>
inline void upd2(T1&a,const T2&b){
    if(a<b)a=b;
}
template<class T>
inline bool equ(const T&a,const T&b){
    return!memcmp(&a,&b,sizeof a);
}
typedef long long ll;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
struct ano{
    operator ll(){
        ll x=0,y=0,c=getchar();
        while(c<48)
            y=c==45,c=getchar();
        while(c>47)
            x=x*10+c-48,c=getchar();
        return y?-x:x;
    }
}buf;
const int N=1e5+5;
char a[N];
int f[26][N];
int main(){
    int t=buf;
    for(int k=1;k<=t;++k){
        printf("Case #%d:\n",k);
        memset(f,0,sizeof f);
        int n=buf,q=buf;
        scanf("%s",a+1);
        for(int i=1;i<=n;++i){
            ++f[a[i]-'A'][i];
            for(int j=0;j<26;++j)
                f[j][i]+=f[j][i-1];
        }
        while(q--){
            int u=buf,v=buf;
            for(int j=0;j<26;++j)
                if(int s=f[j][v]-f[j][u-1]){
                    printf("%d\n",s);
                    break;
                }
        }
    }
}