#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
int t, sum[26][maxn + 10], n, q;
char s[maxn + 10];
int main() {
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas) {
        scanf("%d%d%s", &n, &q, s + 1);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 26; ++j)
                sum[j][i] = sum[j][i - 1];
            ++sum[s[i] - 'A'][i];
        }
        printf("Case #%d:\n", cas);
        while (q--) {
            int l, r; scanf("%d%d", &l, &r);
            for (int i = 0; i < 26; ++i)
                if (sum[i][r] - sum[i][l - 1]) {
                    printf("%d\n", sum[i][r] - sum[i][l - 1]);
                    break;
                }
        }
    }
}