#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 100010
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char c[N];int s[26][N];
int main()
{    int t; cin>>t;
    for(rint T=1;T<=t;T++)
    {    printf("Case #%d:\n",T);
        int n,m,l,r; scanf("%d%d%s",&n,&m,c+1);
        for(rint i=1;i<=n;i++)
        {    s[c[i]-'A'][i]=s[c[i]-'A'][i-1]+1;
            for(rint j=0;j<26;j++) if(j!=c[i]-'A') s[j][i]=s[j][i-1];
        }
        for(rint i=1;i<=m;i++)
        {    scanf("%d%d",&l,&r);
            for(rint j=0;j<26;j++)
            if(s[j][r]-s[j][l-1]){printf("%d\n",s[j][r]-s[j][l-1]);break;}
        }
    }
    return 0;
}