#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
#define fz1(i,n) for (i=1;i<=n;i++)
#define fd1(i,n) for (i=n;i>=1;i--)
#define fz0g(i,n) for (i=0;i<=n;i++)
#define fd0g(i,n) for (i=n;i>=0;i--)
#define fz0k(i,n) for (i=0;i<n;i++)
#define fd0k(i,n) for (i=(long long)(n-1);i>=0;i--)
#define fz(i,x,y) for (i=x;i<=y;i++)
#define fd(i,y,x) for (i=y;i>=x;i--)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len) {char ss[len];scanf(" %s",ss);(st)=ss;}
using namespace std;
int n,m,i,j,cnt[100005][26],t,l,r,cas;
string st;
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        rdst(st,100005);
        st=" "+st;
        fz1(i,st.length()-1)
        {
            memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));
            cnt[i][st[i]-'A']++;
        }
        printf("Case #%d:\n",++cas);
        while (m--)
        {
            scanf("%d%d",&l,&r);
            fz0k(i,26)
            {
                if (cnt[r][i]-cnt[l-1][i]>0)
                {
                    printf("%d\n",cnt[r][i]-cnt[l-1][i]);
                    break;
                }
            }
        }
    }
    return 0;
}