#include<bits/stdc++.h>
#define maxc 26
#define maxn 100050
using namespace std;

int n,m;

char s[maxn];

int cnt[maxn][maxc];

void init()
{
    scanf("%d%d%s",&n,&m,s+1);
    for (int i=1;i<=n;++i)
    {
        memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));
        ++cnt[i][s[i]-'A'];
    }
}

void solve()
{
    while (m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        for (int c=0;c<maxc;++c)
            if (cnt[r][c]!=cnt[l-1][c])
            {
                printf("%d\n",cnt[r][c]-cnt[l-1][c]);
                break;
            }
    }
}

int main()
{
//    freopen("c.in","r",stdin);
    int T,icase=0;
    scanf("%d",&T);
    while (T--)
    {
        printf("Case #%d:\n",++icase);
        init();
        solve();
    }
    return 0;
}