#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int T, n, q, l, r;
char str[maxn];
int cnt[35][maxn];

void func(char ch) {
    for(int i = 1; str[i]; i++) {
        if(str[i] == ch) {
            cnt[ch - 'A'][i] = cnt[ch - 'A'][i - 1] + 1;
        } else {
            cnt[ch - 'A'][i] = cnt[ch - 'A'][i - 1];
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
    scanf("%d", &T);
    for(int Case = 1; Case <= T; ++Case) {
        
        scanf("%d%d", &n, &q);
        scanf("%s", str + 1);
        for(int i = 'A'; i <= 'Z'; ++i)
            func(i);
        printf("Case #%d:\n", Case);
        while(q--) {
            scanf("%d%d", &l, &r);
            for(int i = 0; i < 26; i++) {
                if(cnt[i][r] - cnt[i][l - 1] > 0) {
                    printf("%d\n", cnt[i][r] - cnt[i][l - 1]);
                    break;
                }
            }
        }
    }
    return 0;
}