#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100100,oo=1e9;
int a[maxn],sum[30][maxn],n;
int f[maxn][25],low[maxn];
void init()
{
    for(int i=1;i<=n;i++)
        f[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=26;j++)
            sum[j][i]=(sum[j][i-1]+(a[i]==j));
    int last=1;
    low[1]=0;
    for(int i=2;i<=n;i++)
    {    if(i==last*2)
        {    last=i;
            low[i]=low[i-1]+1;
            continue;
        }
        low[i]=low[i-1];
    }
}
void mem()
{
    for(int i=1;i<=n;i++)
    {    for(int j=0;j<=20;j++)
            f[i][j]=oo;
    }
    memset(sum,0,sizeof(sum));
}
inline int rmq(int l,int r)
{
    int len=r-l+1;
    int k=low[len];
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    //freopen("data.in","r",stdin);
    //freopen("ac.out","w",stdout);
    int T;
    cin>>T;
    int cas=0;
    while(T--)
    {    cas++;
        int q;
        cin>>n>>q;
        mem();
        cin.get();
        for(int i=1;i<=n;i++)
        {    char x;
            cin>>x;
            a[i]=x-'A'+1;
        }
        init();
        cout<<"Case #"<<cas<<":"<<endl;
        while(q--)
        {    int l,r;
            cin>>l>>r;
            int x=rmq(l,r);
            cout<<sum[x][r]-sum[x][l-1]<<endl;
        }
    }
    return 0;
}
/*
查询区间最小值
最小值出现次数 
*/ 
/*
1
30 1
WWHNNAPRWHNZKPOELABRTHTTVVRAAF
1 2
*/