#include <bits/stdc++.h>

using namespace std;

const int Max = 110000;

int num[Max][26];

char str[Max];
int main()
{
    int T;
    int n,q;
    int l,r;
    scanf("%d",&T);
    for(int Case =1; Case<=T;Case++)
    {
        scanf("%d %d",&n,&q);
        scanf("%s",str);
        int len = strlen(str);
        for(int i = 0;i<26;i++) num[0][i] = 0;
        for(int i = 0;i<len;i++)
        {
            for(int j = 0;j<26;j++) num[i+1][j] = num[i][j];
            num[i+1][str[i]-'A'] ++;
        }
        printf("Case #%d:\n",Case);
        while(q--)
        {
            scanf("%d %d",&l,&r);
            int result = 0;
            for(int i = 0;i<26;i++)
            {
                result = num[r][i]-num[l-1][i];
                if(result)
                    break;
            }
            printf("%d\n",result);
        }

    }

    return 0;
}