#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define FOR(i,s,t) for(int i=(s),_t=(t);i<=_t;++i)
#define DOR(i,s,t) for(int i=(s),_t=(t);i>=_t;--i)
#define M 100005

int sum[M][30];
char str[M];
int main() {
    int Cas,n,q;
    scanf("%d",&Cas);
    FOR(t,1,Cas) {
        scanf("%d%d",&n,&q);
        scanf("%s",str+1);
        FOR(i,1,n) {
            FOR(j,0,25) sum[i][j]=sum[i-1][j];
            sum[i][str[i]-'A']++;
        }
        printf("Case #%d:\n",t);
        FOR(i,1,q) {
            int l,r;
            scanf("%d%d",&l,&r);
            FOR(j,0,25) if(sum[r][j]-sum[l-1][j]) {
                printf("%d\n",sum[r][j]-sum[l-1][j]);
                break;
            }
        }
    }
    return 0;
}