#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100005;
int T;
int n,q;
int cnt[N][26];
int main()
{
    for (int u=0;u<26;u++) cnt[0][u]=0;
    scanf("%d",&T);
    for (int TT=1;TT<=T;TT++)
    {
        printf("Case #%d:\n",TT);
        int n,q;
        scanf("%d%d",&n,&q);
        for (int u=1;u<=n;u++)
        {
            for (int i=0;i<26;i++)    cnt[u][i]=cnt[u-1][i];
            char ch=getchar();
            if (ch<'A'||ch>'Z') ch=getchar();
            cnt[u][ch-'A']++;
        }
        while (q--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            for (int u=0;u<26;u++)
            {
                if (cnt[r][u]-cnt[l-1][u]>0)
                {
                    printf("%d\n",cnt[r][u]-cnt[l-1][u]);
                    break;
                }
            }
        }
    }
    return 0;
}