#include <stdio.h>
#include <string.h>
int main()
{
    int t, cas, i, len1, len2, c, len;
    int qNum, strlen;
    int sumAz[100010][30];
    char str[100010];
    scanf("%d", &t);
    for (cas = 1;cas <= t;cas++)
    {
        scanf("%d%d", &strlen, &qNum);
        scanf("%s", str);
        printf("Case #%d:\n", cas);
        for (int i = 0; str[i]; i++) {
            for (int j = 0; j < 26; j++) {
                if (i != 0) {
                    sumAz[i][j] = sumAz[i - 1][j];
                }
                else {
                    sumAz[i][j] = 0;
                }
            }
            sumAz[i][str[i] - 'A']++;
        }
        //for (int i = 0; str[i]; i++) {
        //    for (int j = 0; j < 26; j++) { 
        //        printf("%d ", sumAz[i][j]);
        //    } 
        //    puts("");
        //}

        while (qNum--) {
            int lft, rit;
            scanf("%d%d", &lft, &rit);
            lft--, rit--;
            for (int i = 0; i < 26;i++) {
                int lftNum = 0;
                int ritNum = 0;
                if (lft != 0)
                    lftNum = sumAz[lft - 1][i];
                ritNum = sumAz[rit][i];
                //printf("%d  %d\n", ritNum , lftNum);
                if (ritNum - lftNum != 0) {
                    printf("%d\n", ritNum - lftNum);
                    break;
                }
            }
        }

    }
    return 0;
}