#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100010
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
int i,j,k,l,r,n,q,T,cs,ans;
int wz;
int sum[N][26];
char ch;
int main(){
    scanf("%d",&T);
    cs=0;
    while(T--){
        scanf("%d%d",&n,&q);
        fo(i,1,n){
            fo(j,0,25)sum[i][j]=sum[i-1][j];
            ch=getchar();
            while(ch<'A'||ch>'Z')ch=getchar();
            sum[i][ch-'A']++;
        }
        wz=-1;
        cs++;
        printf("Case #%d:\n",cs);
        fo(i,1,q){
            scanf("%d%d",&l,&r);
            fo(j,0,25)if(sum[r][j]-sum[l-1][j]>0){
                wz=j;
                ans=sum[r][j]-sum[l-1][j];
                break;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}