#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=100005;

int n,m,num[N][26];
char s[N];

void solve()
{
    scanf("%d%d %s",&n,&m,s+1);
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            num[i][j]=num[i-1][j]+(s[i]-'A'==j);
    while(m--)
    {
        int l,r;scanf("%d%d",&l,&r);
        for(int i=0;i<26;i++)
            if(num[r][i]!=num[l-1][i])
            {
                printf("%d\n",num[r][i]-num[l-1][i]);
                break;
            }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("02.in","r",stdin);
    freopen("02.out","w",stdout);
#endif
    int t;cin>>t;
    for(int i=1;i<=t;i++)
        printf("Case #%d:\n",i),solve();
    return 0;
}