#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=100000+5;
char s[maxn];
int T, n, q, l, r;
int dp[maxn][26];

int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        scanf("%d%d", &n, &q);
        scanf("%s", s);
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++){
            int c=s[i-1]-'A';
            for(int j=0;j<26;j++){
                if(j==c)
                    dp[i][j]=dp[i-1][j]+1;
                else dp[i][j]=dp[i-1][j];
            }
        }
        
        for(int i=0;i<q;i++){
            scanf("%d%d", &l, &r);
            int ans, num;
            for(int j=0;j<26;j++){
                num=dp[r][j]-dp[l-1][j];
                if(num>0){
                    ans=num;
                    break;
                }
            }
            if(i==0) cout<<"Case #"<<t<<":"<<endl;
            cout<<ans<<endl;
        }
    }
}