#include<bits/stdc++.h>
using namespace std;


//适用于正负整数
template <class T>
inline bool scan_d(T &ret) {
   char c; int sgn;
   if(c=getchar(),c==EOF) return 0; //EOF
   while(c!='-'&&(c<'0'||c>'9')) c=getchar();
   sgn=(c=='-')?-1:1;
   ret=(c=='-')?0:(c-'0');
   while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
   ret*=sgn;
   return 1;
}
inline void out(int x) {
   if(x>9) out(x/10);
   putchar(x%10+'0');
}

const int maxn = 1e5 + 10;

int f[26][maxn];
char s[maxn];

int main(){
    int t;
    int T = 1;
    scan_d(t);
    while (T <= t) {
        int n, q;
        scan_d(n);
        scan_d(q);
        scanf("%s", s + 1);
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++) {
            int w = s[i] - 'A';
            for (int j = 0; j < 26; j++) {
                f[j][i] = f[j][i - 1] + ((j == w)?1:0);
            }
        }
        printf("Case #%d:\n", T);T++;
        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if (f[i][r] - f[i][l - 1] > 0) {
                    ans = f[i][r] - f[i][l-1];
                    break;
                }
            }
            out(ans);
            printf("\n");
        }
    }
    return 0;
}