#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
#define mst(a,x) memset(a,x,sizeof(a))
#define For(i, t) for(int i = 0; i < t; i++)
#define Debug(x) cerr << #x << " = "  << x << endl;
using namespace std;

const int N = 1e5 + 5;
int n, m, cnt[N][26];
char s[N];

int main(){
    int T;
    scanf("%d", &T);
    For(cas, T) {
        scanf("%d%d", &n, &m);
        scanf("%s", s + 1);
        For(i, 26) cnt[0][i] = 0;
        for(int i = 1; i <= n; i++) {
            For(j, 26) cnt[i][j] = cnt[i - 1][j];
            cnt[i][s[i] - 'A']++;
        }
        printf("Case #%d:\n", cas + 1);
        while(m--) {
            int l, r;
            scanf("%d%d", &l, &r);
            For(i, 26) { 
                int t = cnt[r][i] - cnt[l - 1][i];
                if(t) {
                    printf("%d\n", t);
                    break;
                }

            }
        }
    }
    return 0;
}