#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100010
using namespace std;
int T,n,m;
char s[maxn];
struct P{
    int num,sum;
}t[maxn*4];
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k].num=s[l]-'A';
        t[k].sum=1;
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    t[k].num=min(t[k*2].num,t[k*2+1].num);
    t[k].sum=(t[k*2].num==t[k].num)*t[k*2].sum+(t[k*2+1].num==t[k].num)*t[k*2+1].sum; 
}
int ans1,ans2;
void query(int k,int l,int r,int x,int y)
{
    if(l>=x&&r<=y)
    {
        if(t[k].num==ans1)  ans2+=t[k].sum;
        if(t[k].num<ans1)
        {
            ans1=t[k].num;
            ans2=t[k].sum;
        }
        return;
    }
    int mid=(l+r)/2;
    if(mid>=x)  query(k*2,l,mid,x,y);
    if(mid<y)   query(k*2+1,mid+1,r,x,y);
}
int main()
{
    //freopen("2.in","r",stdin);
    scanf("%d",&T);
    int o=T;
    while(T--)
    {
        memset(t,0,sizeof(t));
        scanf("%d%d",&n,&m); 
        scanf("%s",s+1);
        build(1,1,n);
        printf("Case #%d:\n",o-T);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            ans1=100;ans2=0;
            query(1,1,n,x,y); 
            printf("%d\n",ans2);
        }
    }
    return 0;
}