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

const int MAXN=1e5+10;

int sum[MAXN][30],n,m;
char ch[MAXN];

int main(){
    int T,cas=0; scanf("%d",&T);
    while(T--){
        memset(sum,0,sizeof(sum));
        scanf("%d%d",&n,&m);
        scanf("%s",ch+1);
        for(int i=1;i<=n;i++){
            for(int j=0;j<26;j++)
                if (ch[i]-'A'==j) sum[i][j]=sum[i-1][j]+1;
                else sum[i][j]=sum[i-1][j];
        }
        printf("Case #%d:\n",++cas);
        for(int i=1;i<=m;i++){
            int l,r; scanf("%d%d",&l,&r);
            for(int j=0;j<26;j++)
                if (sum[r][j]-sum[l-1][j]!=0){
                    printf("%d\n",sum[r][j]-sum[l-1][j]);
                    break;
                }            
        }
    }
    return 0;
}