#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int cas,n,q,i,j,l,r,sum[M][26];
char s[M];
int main(){
    scanf("%d",&cas);
    for (int Cas=1;Cas<=cas;Cas++){
        scanf("%d%d",&n,&q);
        scanf("%s",s);
        for (i=1;i<=n;i++){
            for (j=0;j<26;j++)sum[i][j]=sum[i-1][j];
            sum[i][s[i-1]-'A']++;
        }
        printf("Case #%d:\n",Cas);
        while (q--){
            scanf("%d%d",&l,&r);
            for (i=0;i<26;i++)
                if (sum[r][i]>sum[l-1][i]){
                    printf("%d\n",sum[r][i]-sum[l-1][i]);
                    break;
                }
        }
    }
}