#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define out(a) printf("%d\n",a)
#define clr(x,y) memset(x,y,sizeof(x))
inline ll read(){
    ll f=1,x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
/*------------------------------------------------------------*/
#define mod 10007
#define maxn 100010
#define inf (1<<30)
/*------------------------------------------------------------*/
char c[maxn];
int s[maxn][30];
int main(){
    int t;
    in(t);
    FOR(q,1,t){
        int n,m;
        in(n);in(m);
        scanf("%s",c+1);
        FOR(i,1,n){
            FOR(j,0,25)s[i][j]=s[i-1][j];
            s[i][c[i]-'A']++;
        }
        printf("Case #%d:\n",q); 
        while(m--){
            int l,r;
            in(l);in(r); 
            FOR(i,0,25){
                if(s[r][i]-s[l-1][i]){
                    out(s[r][i]-s[l-1][i]);
                    break;
                }
            }
        }
    }
}