#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int t,n,q,sum[30][maxn];
char s[maxn];
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            int x=s[i]-'A';
            for(int j=0;j<26;j++)
            {
                sum[j][i]=sum[j][i-1];
            }
            sum[x][i]++;
        }
        printf("Case #%d:\n",k);
        while(q--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            for(int i=0;i<26;i++)
            {
                int num=sum[i][r]-sum[i][l-1];
                if(num)
                {
                    printf("%d\n",num);
                    break;
                }
            }
        }
    }
    return 0;
}