#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <iostream>
#include <bitset>
#define REP(i,a,b)for (int i=a;i<=b;++i)
#define PER(i,a,b)for (int i=a;i>=b;--i)
#define RVC(i,S)for (int i=0;i<S.size();++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef pair<int,int> pii;
typedef long long LL;
typedef vector<int> VI;

int n,q,cnt[100005][26];
char str[100005];
void solve(){
    scanf("%d%d",&n,&q);
    scanf("%s",str+1);
    memset(cnt,0,sizeof cnt);
    REP(i,1,n){
        str[i]-='A';
        REP(j,0,25)cnt[i][j]=cnt[i-1][j];
        cnt[i][str[i]]++;
    }
    REP(i,1,q){
        int l,r;
        scanf("%d%d",&l,&r);
        int c=0;
        REP(j,0,25)if(cnt[r][j]-cnt[l-1][j]){
            c=j;break;
        }
        printf("%d\n",cnt[r][c]-cnt[l-1][c]);
    }
}

int main(){
    int T;scanf("%d",&T);
    REP(i,1,T){
        printf("Case #%d:\n",i);
        solve();
    }
    return 0;
}