#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5+10;
int c[30][maxn];
inline int lowbit(int x){
    return x&-x;
}
int add(int i,int x){
    while(x<maxn){
        c[i][x]++;
        x+=lowbit(x);
    }
    return 0;
}
int reset(int i,int x){
    while(x<maxn){
        c[i][x]=0;
        x+=lowbit(x);
    }
    return 0;
}
int sum(int i,int x){
    int ret=0;
    while(x>0){
        ret+=c[i][x];
        x-=lowbit(x);
    }
    return ret;
}
char s[maxn];
vector<pair<int,int> > record;
void clear(){
    for(int i=0;i<record.size();i++){
        reset(record[i].first,record[i].second);
    }
    record.clear();
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++){
        printf("Case #%d:\n",kase);
        int n,q;
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        for(int x=1;x<=n;x++){
            int i = s[x]-'A';
            add(i,x);
            record.push_back(make_pair(i,x));
        }
        int l,r;
        while(q--){
            scanf("%d%d",&l,&r);
            int ans=0;
            for(int i=0;i<26;i++){
                ans = sum(i,r)-sum(i,l-1);
                if(ans>0){
                    break;
                }
            }
            printf("%d\n",ans);
        }
        clear();
    }
    return 0;
}