# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL int Input(){
    RG int x = 0, z = 1; RG char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * z;
}

const int maxn(1e5 + 5);

int n, q, sum[26][maxn];
char s[maxn];

int main(){
    for(RG int t = Input(), testcase = 1; testcase <= t; ++testcase){
        printf("Case #%d:\n", testcase);
        Fill(sum, 0), n = Input(), q = Input();
        scanf(" %s", s + 1);
        for(RG int i = 1; i <= n; ++i)
            for(RG int j = 0; j < 26; ++j) sum[j][i] = sum[j][i - 1] + (s[i] - 'A' == j);
        for(RG int i = 1; i <= q; ++i){
            RG int l = Input(), r = Input();
            for(RG int j = 0; j < 26; ++j)
                if(sum[j][r] - sum[j][l - 1]){
                    printf("%d\n", sum[j][r] - sum[j][l - 1]);
                    break;
                }
        }
    }
    return 0;
}