#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100005

using namespace std;

int T,n,q,sum[26][maxn];
char s[maxn];

int main()
{
    int Case=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&q);
        scanf("%s",&s);
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<26;j++) sum[j][i+1]=sum[j][i];
            sum[s[i]-'A'][i+1]++;
        }
        printf("Case #%d:\n",Case++);
        int l,r;
        while (q--)
        {
            scanf("%d%d",&l,&r);
            int i=0;
            while (sum[i][r]-sum[i][l-1]<=0 && i<26) i++;
            printf("%d\n",sum[i][r]-sum[i][l-1]);
        }
    }
    return 0;
}