#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 100010;
int sum[Maxn][26];
char s[Maxn];
int n, Q;
int main() {
    int i, j, k;
    int T, Ti = 0;
    scanf("%d", &T);
    while(T--){
        printf("Case #%d:\n", ++Ti);
        scanf("%d%d", &n, &Q);
        scanf("%s", s+1);
        for(i = 1; i <= n; i++){
            for(j = 0; j < 26; j++) sum[i][j] = sum[i-1][j];
            sum[i][s[i]-'A']++;
        }
        for(i = 1; i <= Q; i++){
            int l, r;
            scanf("%d%d", &l, &r);
            for(j = 0; j < 26; j++) if(sum[r][j]-sum[l-1][j] > 0) break;
            printf("%d\n", sum[r][j]-sum[l-1][j]);
        }
    }
    return 0;
}