#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)
#define rep1(i,e) for(int i=1;i<=(e);i++)
#define repx(i,x,e) for(int i=(x);i<=(e);i++)
#define pii pair<int,int>
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

typedef long long ll;
template <class T>
void test(T a){cout<<a<<endl;}
template <class T,class T2>
void test(T a,T2 b){cout<<a<<" "<<b<<endl;}
template <class T,class T2,class T3>
void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int pre[30][N];
char s[N];

int T = 1;
void work(){
    printf("Case #%d:\n", T++);
    int n, m;
    cin >> n >> m;
    cin >> s;
    rep1(i,n){
        rep(j,26){
            if(s[i-1]-'A' == j){
                pre[j][i] = pre[j][i-1] + 1;
            }
            else{
                pre[j][i] = pre[j][i-1];
            }
        }
    }
    for(;m--;){
        int l, r;
        cin >> l >> r;
        rep(i,26){
            if(pre[i][r] - pre[i][l-1] > 0){
                printf("%d\n", pre[i][r] - pre[i][l-1]);
                break;
            }
        }
    }
}

int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    IOS;
    int t;
//    scd(t);
    cin >> t;
    for(;t--;){
        work();
    }
//    work();
}