/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define LOCAL

void qread(int &x){
    int neg=1;x=0;
    char c=getchar(); 
    while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    x*=neg;
}

const int maxn=100005;
int test,n,q;
int sum[maxn][30];
string s;
char c[maxn];

int main(){
#ifndef LOCAL
    freopen("FILE.in","r",stdin);
    freopen("FILE.out","w",stdout);
#endif
    scanf("%d",&test);
    REP(t,test){
        scanf("%d%d%s",&n,&q,c);
        s=c;n=s.size();
        memset(sum,0,sizeof(sum));
        rep(i,n){
            rep(j,26)sum[i+1][j]=sum[i][j]+(s[i]-'A'==j);
        }
        printf("Case #%d:\n",t);
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            rep(i,26)if(sum[r][i]-sum[l-1][i]>0){
                printf("%d\n",sum[r][i]-sum[l-1][i]);
                break;
            } 
        }
    }
    return 0;
}

/*
Input:
-----------------
Output:
*/