#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10;
char str[maxn];
int sum[26][maxn];
int main() {
    int T;
    scanf("%d", &T);
    for (int c = 1; c <= T; c++) {
        int n, m, l, r;
        scanf("%d%d", &n, &m);
        scanf("%s", str + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                sum[j][i] = sum[j][i - 1];
            }
            sum[str[i] - 'A'][i]++;
        }
        printf("Case #%d:\n", c);
        while (m--) {
            scanf("%d%d", &l, &r);
            for (int i = 0; i < 26; i++) {
                int ans = (sum[i][r] - sum[i][l - 1]);
                if (ans > 0) {
                    printf("%d\n", ans);
                    break;
                }
            }
        }
    }
    return 0;
}