#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
using namespace std;

const int maxn = 100005;
int sum[maxn][26], n, Q, l, r, ans;
char s[maxn];

int main() {
    int T, Case = 0;
    scanf("%d", &T);
    while (T--) {
        printf("Case #%d:\n", ++Case);
        scanf("%d%d%s", &n, &Q, s + 1);
        n = strlen(s + 1);
        rep (i, 1, n) {
            rep (j, 0, 25) sum[i][j] = sum[i-1][j];
            sum[i][s[i]-'A']++;
        }
        while (Q--) {
            scanf("%d%d", &l, &r);
            rep (i, 0, 25) 
                if (sum[r][i] - sum[l-1][i]) {
                    ans = sum[r][i] - sum[l-1][i];
                    break;
                }
            printf("%d\n", ans);
        }
    }
    
    return 0;
}