#include <cstdio>
#include <algorithm>

int T;
int n, q;
char s[200000];
int cnt[200000][26];

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