#include<cstdio>
#include<cctype>
#define maxn 100005
int n,q,s[maxn][26],x,y;
char a[maxn];
void get(int &a)
{
    char c;a=0;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) a=a*10+c-'0',c=getchar();
}
int main()
{
    int kase;
    get(kase);
    for(int o=1;o<=kase;o++)
    {
        printf("Case #%d:\n",o);
        get(n),get(q);
        scanf("%s",a+1);
        for(int i=1;i<=n;i++)
            for(int j=0;j<26;j++)
                s[i][j]=s[i-1][j]+(a[i]-'A'==j);
        for(int i=1;i<=q;i++)
        {
            get(x),get(y);
            for(int j=0;j<26;j++)
                if(s[y][j]-s[x-1][j]>0) {printf("%d\n",s[y][j]-s[x-1][j]);break;}
        }
    }
}