#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define forx(i,a,b) for(i=a;i<b;i++)
using namespace std;
const int maxn=1e5+11;
char str[maxn];
int qz[maxn][33];
int main()
{
    int T,t=0,len;
    scanf("%d",&T);
    while(T--)
    {
        int n,q;
        scanf("%d%d%s",&n,&q,str);
        int i,j;
        len=strlen(str);
        forx(i,0,len)
        {
            forx(j,0,26)
            {
                qz[i+1][j]=qz[i][j];
            }
            qz[i+1][str[i]-'A']++;
        }
        printf("Case #%d:\n",++t);
        while(q--)
        {
            int L,R;
            scanf("%d%d",&L,&R);
            forx(i,0,26)
            {
                if(qz[R][i]-qz[L-1][i]>0)
                {
                    printf("%d\n",qz[R][i]-qz[L-1][i]);
                    break;
                }
            }
        }
    }
    return 0;
}