#include <bits/stdc++.h>

using namespace std;

int t, n, q, y[100005][26];
char x[100005];
int ta, tb, tc;

int main() {
    scanf("%d", &t);
    for (int tt = 1; tt <= t; tt++) {
        scanf("%d%d%s", &n, &q, x);
        for (int i = 0; i < n; i++) {
            memcpy(y[i + 1], y[i], sizeof(y[i]));
            y[i + 1][x[i] - 'A']++;
        }
        printf("Case #%d:\n", tt);
        while (q--) {
            scanf("%d%d", &ta, &tb);
            ta--;
            for (int i = 0; ; i++) {
                tc = y[tb][i] - y[ta][i];
                if (tc) {
                    printf("%d\n", tc);
                    break;
                }
            }
        }
    }
    return 0;
}