#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 100;
int cnt[27][N];
char st[N];
int main(){
    int T, ca = 0;
    cin >> T;
    while (T --){
        int n, q;
        scanf("%d%d", &n, &q);
        scanf("%s", st + 1);
        for (int i = 1; i <= n; i ++){
            for (int j = 0; j < 26; j ++)
                cnt[j][i] = cnt[j][i - 1] + (st[i] == 'A' + j);
        }
        printf("Case #%d:\n", ++ ca);
        while (q --){
            int l, r, ans;
            scanf("%d%d", &l, &r);
            for (int i = 0; i < 26; i ++) if (cnt[i][r] - cnt[i][l - 1]){
                ans = cnt[i][r] - cnt[i][l - 1];
                break;
            }
            printf("%d\n", ans);
        }
    }
}