#include <bits/stdc++.h>
using namespace std;


int n, q;
char s[100005];
int su[100005][26];

void work() {
    cin >> n >> q;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            su[i][j] = su[i - 1][j] + (s[i] == j + 'A');
        }
    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l , &r);
        for (int j = 0; j < 26; j++) {
            if (su[r][j] - su[l - 1][j]) {
                printf("%d\n", su[r][j] - su[l - 1][j]);
                break;
            }
        }
    }
}


int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        printf("Case #%d:\n", i);
        work();
    }
}