#include<stdio.h>
#include<string.h>
char s[100005];
int sum[100005][26];
int main()
{
    int cas,n,q,l,r,t,i,c;
    scanf("%d",&cas);
    for(t=1;t<=cas;t++)
    {
        scanf("%d%d",&n,&q);
        scanf("%s",s);
        memset(sum[0],0,sizeof(sum[0]));
        for(i=1;i<=n;i++)
        {
            memcpy(sum[i],sum[i-1],sizeof(sum[0]));
            sum[i][s[i-1]-'A']++;
        }
        printf("Case #%d:\n",t);
        while(q--)
        {
            scanf("%d%d",&l,&r);
            for(c=0;c<26;c++)if(sum[r][c]-sum[l-1][c]>0)break;
            printf("%d\n",sum[r][c]-sum[l-1][c]);
        }
    }
    return 0;
}