#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int tot[26][N];
char s[N];
int main() {
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        scanf("%s", s);
        memset(tot, 0, sizeof(tot));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 26; ++j)
                tot[j][i] = tot[j][i - 1];
            tot[s[i] - 'A'][i]++;
        }


        printf("Case #%d:\n", cas++);
        while (m--) {
            int l, r;
            scanf("%d%d", &l, &r);
            l--, r--;
            for (int i = 0; i < 26; ++i) {
                int tmp;
                if (l == 0) tmp = tot[i][r];
                else tmp = tot[i][r] - tot[i][l - 1];
                if (tmp > 0) {
                    printf("%d\n", tmp);
                    break;
                }
            }
        }
    }
    return 0;
}