#include <bits/stdc++.h>
using namespace std;
const int maxn=112345;
int T,n,q,l,r,cnt[maxn][26];
char s[maxn];
int main()
{
    scanf("%d",&T);
    for (int cas=1;cas<=T;++cas) {
        printf("Case #%d:\n",cas);
        scanf("%d%d%s",&n,&q,s+1);
        for (int i=0;i<26;++i)
            for (int j=1;j<=n;++j)
                cnt[j][i]=0;
        for (int i=1;i<=n;++i)
            cnt[i][s[i]-'A']=1;
        for (int i=0;i<26;++i)
            for (int j=1;j<=n;++j)
                cnt[j][i]+=cnt[j-1][i];
        while (q--) {
            scanf("%d%d",&l,&r);
            for (int i=0;i<26;++i)
                if (cnt[r][i]-cnt[l-1][i]>0) {
                    printf("%d\n",cnt[r][i]-cnt[l-1][i]);
                    break;
                }
        }
    }
    return 0;
}
/*
10
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
*/