#include <bits/stdc++.h>
#define LL long long
#define N 105000
#define C 30
using namespace std;

inline LL read(){
    LL x = 0,f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
    while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}

inline void write(LL x){
    LL k = 0,lx = x;char put[40];
    if (lx ==0) putchar('0');
    if (lx < 0) putchar('-'),lx = -lx;
    while (lx)  put[++k] = (lx % 10) + '0',lx /= 10;
    while (k)   putchar( put[ k-- ] );
    putchar('\n');
}

inline int Get(){
    char c = getchar();
    while ( (c < 'A' || c > 'Z') && (c != EOF) ) c = getchar();
    return c - 'A' + 1;
}

int T,n,q,l,r,ttt;
LL f[N][C];

void init(){
    n = read(); q = read();
    for (int i = 0; i <= 27; ++i) f[0][i] = 0;
    
    int z;
    
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= 27; ++j) f[i][j] = f[i-1][j];
        z = Get();
        ++f[i][z];
    }
}

void solve(){
    int ttt;
    
    while (q--){
        l = read(),r = read();
        ttt = 0;
        for (int i = 0; i <= 27; ++i)
            if (f[r][i] - f[l-1][i]) {ttt = f[r][i] - f[l-1][i];break;}
        write(ttt);
    }
}

int main(){
    T = read();
    for (int t = 1; t <= T; ++t){
        init();
        printf("Case #%d:\n",t);
        solve();
    }
    return 0;
}