#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char ch[111111];

int S[27][111111];

int main() {
    int T;
    scanf("%d", &T);
    for(int TT = 1; TT <= T; TT++) {
        printf("Case #%d:\n", TT);
        int n, q;
        scanf("%d%d", &n, &q);
        scanf("%s", ch + 1);
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 26; j++) S[j][i] = S[j][i - 1];
            S[ch[i] - 'A'][i]++;
        }
        while(q--) {
            int a, b;
            scanf("%d%d", &a, &b);
            for(int i = 0; i < 26; i++) if(S[i][a - 1] != S[i][b]) {
                printf("%d\n", S[i][b] - S[i][a - 1]);
                break;
            }
        }
    }
    return 0;
}