#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
    static ui seed=416;
    return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 233333;
int n,m,cnt[26][100002];char s[N];
int main() {
    int T;read(T);
    rep(Case,1,T){
        read(n);read(m);scanf("%s",s+1);
        rep(i,0,25)rep(j,1,n)cnt[i][j]=cnt[i][j-1]+(s[j]=='A'+i);
        printf("Case #%d:\n",Case);
        while(m--){
            int l,r;read(l);read(r);
            rep(i,0,25)if(cnt[i][r]-cnt[i][l-1]){
                printf("%d\n",cnt[i][r]-cnt[i][l-1]);break;
            }
        }
    }
    return 0;
}