#include<bits/stdc++.h>
using namespace std;
typedef long long LL;


int ct[30][100005];
int main()
{
    int T;
    scanf("%d",&T);
    for(int case_t=1;case_t<=T;case_t++)
    {
        int n,q;
        char s[100007];
        scanf("%d%d",&n,&q);
        scanf("%s",s);
        memset(ct,0,sizeof(ct));
        for(int i=1;i<=n;i++)
        {
            ct[s[i-1]-'A'][i-1]++;
            for(int j=0;j<26;j++)
                ct[j][i]=ct[j][i-1];
        }
        printf("Case #%d:\n",case_t);
        for(int i=0;i<q;i++)
        {
            int l,r;
            scanf("%d %d",&l,&r);
            l--,r--;
            int ans=0;
            for(int i=0;i<26;i++)
            {
                if(l==0)
                {
                    if(ct[i][r]>0)
                    {
                        ans=ct[i][r];
                        break;
                    }
                }
                else if(ct[i][r]-ct[i][l-1]>0)
                {
                    ans=ct[i][r]-ct[i][l-1];
                    break;
                }
            }
            printf("%d\n",ans);
        }
    }

}