#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define MAXP 18
#define MAXN 100006
#define LETTER 26
using namespace std;

int minv[MAXN][MAXP];
int g[LETTER][MAXN];
char s[MAXN];


int T;
int N,M;

int MIN(int x,int y)
{
    return x<y?x:y;
}


int query(int x,int y)
{
    int now=x;
    int res=s[x] - 'A';

    for(int i=MAXP-1; i>=0;i--)
    {
        int offset = 1<<i;
        if(now + offset - 1 <= y)
        {
            res = MIN(res, minv[now][i]);
            now += offset;
        }
    }

    return res;
}


int main()
{
    //freopen("test.in","r",stdin);

    scanf("%d",&T);
    int no=0;
    while(T--)
    {
        no++;
        memset(minv,-1,sizeof(minv));
        memset(g,0,sizeof(g));

        printf("Case #%d:\n",no);

        scanf("%d%d",&N,&M);
        scanf("%s",s);

        for(int i=0;i<N;i++)
        {
            int lid = s[i] - 'A';

            minv[i][0] = lid;

            for(int j=0;j<LETTER;j++)
            {
                if(j == lid)g[j][i + 1] = g[j][i]+1;
                else g[j][i + 1] = g[j][i];
            }
        }

        for(int p = 1; p < MAXP ; p++)
            for(int i=0;i<N;i++)
            {
                int offset = 1<<p;

                if(i + offset > N)break;

                int j = i + offset/2;

                minv[i][p] = MIN(minv[i][p-1], minv[j][p-1]);

            }

        for(int i=1;i<=M;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int min_id = query(x-1, y-1);
            int ans = g[min_id][y] - g[min_id][x-1];
            printf("%d\n",ans);
        }
    }
    return 0;
}