#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const int mod = 1e9+7;
char s[maxn];
int t[maxn][26];
int main(){
    int T, kase = 0;
    scanf("%d", &T);
    while(T--){
        int n, q;
        scanf("%d%d", &n, &q);
        scanf("%s", s+1);
        int len = strlen(s+1);
        //cout << len << endl;
        for(int i = 1; i <= len; ++i){
            for(int j = 0; j < 26; ++j){
                t[i][j] = t[i-1][j] + (s[i]-'A'==j?1:0);
            }
        }
        printf("Case #%d:\n", ++kase);
        while(q--){
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = 0;
            for(int i = 0; i < 26; ++i){
                if(t[r][i]-t[l-1][i] > 0){
                    ans = t[r][i]-t[l-1][i];
                    break;
                }
            }
            printf("%d\n", ans);
        }
    }
}