#include <cstdio>
#include <algorithm>

int n, q;
char s[100009];
int b[100009][26];

int main()
{
    int T;
    scanf("%d", &T);
    for(int tt=1; tt<=T; tt++)
    {
        printf("Case #%d:\n", tt);
        scanf("%d%d%s", &n, &q, s);
        for(int i=1; i<=n; i++) for(int j=0; j<26; j++) b[i][j]=b[i-1][j]+(s[i-1]==j+'A');
        while (q--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans=0; while (b[r][ans]-b[l-1][ans]==0) ans++;
            printf("%d\n", b[r][ans]-b[l-1][ans]);
        }
    }
    return 0;
}