#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T&x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc

const int N=1e5+5;
int cnt[N][26];

int main()
{
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    int tt;
    cin>>tt;
    rep(case_id,1,tt)
    {
        int n,m;
        cin>>n>>m;
        rep(i,1,n)
        {
            char c;
            cin>>c;
            rep(j,0,25)cnt[i][j]=cnt[i-1][j]+(c=='A'+j);
        }
        printf("Case #%d:\n",case_id);
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int i=0;
            while(cnt[l-1][i]==cnt[r][i])++i;
            printf("%d\n",cnt[r][i]-cnt[l-1][i]);
        }
    }
}