#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N  100006
int a[50][N];
char str[N];
int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,e,f;
        scanf("%d%d%s",&n,&m,str);
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            int w=str[i]-'A';
            for(int j=0;j<26;j++)
            {
                if(w==j)
                    a[j][i+1]=a[j][i]+1;
                else a[j][i+1]=a[j][i];
            }
        }
        printf("Case #%d:\n",t++);
        while(m--)
        {
            scanf("%d%d",&e,&f);
            for(int i=0;i<26;i++)
            {
                if(a[i][f]-a[i][e-1]!=0)
                {
                    printf("%d\n",a[i][f]-a[i][e-1]);
                    break;
                }
            }
        }
    }
    return 0;
}