/* ***********************************************
Author        :yang12138
Created Time  :2018年08月04日 星期六 20时53分03秒
File Name     :1002.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=1e5+10;

int sum[N][26];
char s[N];

void solve(int t){
    int n,Q;
    scanf("%d%d",&n,&Q);

    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++) sum[i][j]=sum[i-1][j];
        sum[i][s[i]-'A']++;
    }
    printf("Case #%d:\n",t);
    while(Q--){
        int l,r;
        scanf("%d%d",&l,&r);
        for(int i=0;i<26;i++){
            int ans=sum[r][i]-sum[l-1][i];
            if(ans){
                printf("%d\n",ans);
                break;
            }
        }
    }

}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
    int T,t=0;
    scanf("%d",&T);
    while(T--) solve(++t);
    return 0;
}