#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+233;
char s[maxn];
int T,n,q,l,r,ans,tot=1;
int c[26][maxn];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int c[])
{
    while(x<=n)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
int getsum(int x,int c[])
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int fun(int l,int r,std::string s)
{
    int num=0;
    char c=s[l-1];
    //cout<<"c1="<<c<<endl;
    for(int i=l-1; i<r; ++i)
    {
        if(s[i]<=c)
            c=s[i];
    }
    //cout<<"c2="<<c<<endl;
    for(int i=l-1; i<r; ++i)
    {
        if(s[i]==c)
            num++;
    }
    return num;
    //cout<<"num= "<<num<<endl;
}
int main()
{
    //fun(1,2,s);
    //freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        printf("Case #%d:\n",tot++);
        ans=0;
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        memset(c,0,sizeof(c));
        for(int j=1; j<=n; ++j)
        {
            update(j,c[s[j]-'A']);
        }
        for(int i=0; i<q; ++i)
        {
            scanf("%d%d",&l,&r);
            for(int j=0; j<26; ++j)
            {
                ans=getsum(r,c[j])-getsum(l-1,c[j]);
                if(ans)
                {
                    printf("%d\n",ans);
                    break;
                }
            }
        }
    }
    return 0;
}