#include<bits/stdc++.h>
using namespace std;
int i,q,n,I,L,R,T;
pair<char,int> st[400010];
char S[100010];
pair<char,int> M(pair<char,int> x,pair<char,int> y)
{
    if(x.first==y.first)return x.second+=y.second,x;
    return min(x,y);
}
void B(int x,int l,int r)
{
    if(l==r)st[x]=make_pair(S[l],1);
    else
    {
        int m=l+r>>1;
        B(x*2,l,m);
        B(x*2+1,m+1,r);
        st[x]=M(st[x*2],st[x*2+1]);
    }
}
pair<char,int> Q(int x,int l,int r)
{
    if(L<=l&&r<=R)return st[x];
    int m=l+r>>1;
    if(R<=m)return Q(x*2,l,m);
    if(L>m)return Q(x*2+1,m+1,r);
    return M(Q(x*2,l,m),Q(x*2+1,m+1,r));
}
main()
{
    cin>>T;
    while(T--)
    {
        printf("Case #%d:\n",++I);
        cin>>n>>q;
        scanf("%s",S+1);
        B(1,1,n);
        for(i=1;i<=q;i++)scanf("%d%d",&L,&R),printf("%d\n",Q(1,1,n).second);
    }
}