/*************************************************************************
    > File Name: 1002.cpp
    > Author: yuki
    > ################### 
    > Mail: ################### 
    > Created Time: Sun 05 Aug 2018 08:40:19 PM CST
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<cmath>
using namespace std;
 /*MACRO*/
#define FORi(l,r) for(int i=(l);i<(r);i++)
#define FORj(l,r) for(int j=(l);j<(r);j++)
#define FORk(l,r) for(int k=(l);k<(r);k++)
#define MEMSET0(i) memset((i),0,sizeof((i)))
#define MEMSET1(i) memset((i),-1,sizeof((i)))

int num[100005][30];

int main()
{
    int t;
    scanf("%d", &t);
    for(int tt=1; tt<=t; tt++)
    {
        int n, q;
        scanf("%d%d", &n, &q);
        char s[100005]={0};
        scanf("%s", s+1);
        memset(num, 0, sizeof(num));
        for(int i=1; i<=n; i++)
        {
            for(int j='A'; j<='Z'; j++)
                num[i][j-'A']=num[i-1][j-'A'];
            num[i][s[i]-'A']++;
        }
        printf("Case #%d:\n", tt);
        while(q--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            int tmp[30]={0}, ans=0;
            for(int i='A'; i<='Z'; i++)
            {
                tmp[i-'A']=num[r][i-'A']-num[l-1][i-'A'];
                if(tmp[i-'A'] > 0)
                {
                    ans=tmp[i-'A'];
                    break;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}