#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const ll infl = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MAXN = 100005;

int n, q;
char s[MAXN];
int pre[MAXN][30];

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input.txt", "r", stdin);
#endif
    int T; scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        scanf("%d %d", &n, &q);
        scanf("%s", s + 1);
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i <= n; ++i) {
            int p = s[i] - 'A';
            for(int j = 0; j < 30; ++j) {
                pre[i][j] = pre[i - 1][j];
            }
            pre[i][p] = pre[i - 1][p] + 1;
        }
        int l, r, cnt[30];
        printf("Case #%d:\n", cas);
        while(q --) {
            scanf("%d %d", &l, &r);
            int res = 0;
            for(int i = 0; i < 30; ++i) {
                cnt[i] = pre[r][i] - pre[l - 1][i];
                if(cnt[i] == 0) continue;
                res = cnt[i];
                break;
            }
            printf("%d\n", res); 
        }
    }
    return 0;
}