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

const int N = 1e5 + 10;
int sum[N][26];
int cas = 0;
char s[N];
int main() {
    int T;
    cin >> T;
    while(T --) {
        printf("Case #%d:\n", ++ cas);
        int n, Q;
        scanf("%d %d", &n, &Q);
        scanf("%s", s + 1);
        for(int i = 1; i <= n; i ++) {
            for(int ch = 0; ch < 26; ch ++) {
                sum[i][ch] = sum[i - 1][ch] + (s[i] == 'A' + ch);
            }
        }    

        for(int i = 1; i <= Q; i ++) {
            int l, r;
            scanf("%d %d", &l, &r);
            for(int ch = 0; ch < 26; ch ++) {
                if(sum[r][ch] - sum[l - 1][ch]) {
                    printf("%d\n", sum[r][ch] - sum[l - 1][ch]);
                    break;
                }
            }
        }
    }
}