/*=================================
# Created time: 2018-08-04 12:53
# Filename: b.cpp
# Description: 
=================================*/
#include <bits/stdc++.h> 
 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back 
#define lb lower_bound 
#define ub upper_bound 
#define sqr(x) (x)*(x) 
#define lowbit(x) (x)&(-x) 
#define pii pair<int, int> 
#define ls(a,b) (((a)+(b)) << 1) 
#define rs(a,b) (((a)+(b)) >> 1) 
#define fin(a) freopen(a,"r",stdin); 
#define fout(a) freopen(a,"w",stdout); 
#define FORP(i,a,b) for(int i=(a);i<=(b);i++) 
#define FORM(i,a,b) for(int i=(a);i>=(b);i--) 
 
#define maxn 100005 
#define maxm 100005 
#define MOD 1000000007 
#define INF 1070000000 
using namespace std; 
typedef long long ll; 
typedef unsigned long long ull; 
 
template<class T> inline   
void read(T& num){   
    num = 0; bool f = 1;char ch = getchar();   
    while(ch < '0' || ch > '9') { if(ch == '-') f = 0;ch = getchar();}   
    while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();}   
    num = f ? num: -num;   
}  
template<class T> inline 
void write(T x,char ch){ 
    int s[100]; 
    if (x==0) {putchar('0'); putchar(ch); return;} 
    if (x<0) {putchar('-'); x=-x;} int num=0; 
    while (x){ s[num++]=(x%10); x=x/10;} 
    FORM(i,num-1,0) putchar(s[i]+'0'); putchar(ch); 
} 
/*==================split line==================*/ 
const double pi = acos(-1); 
const double eps = 1e-8; 
int sum[maxn][30];
char s[maxn];
int n, q;
int main(){ 
    //fin("b.in");
    int cas, T = 1; read(cas);
    while(cas--){
        printf("Case #%d:\n", T); T++;
        memset(sum, 0, sizeof(sum));
        read(n); read(q); scanf("%s",s + 1);
        FORP(i, 1, n){
            FORP(j, 1, 26) sum[i][j] += sum[i - 1][j];
            sum[i][s[i] - 'A' + 1]++;
        }
        FORP(i, 1, q){
            int l, r;
            read(l); read(r);
            FORP(j, 1, 26) 
                if (sum[r][j] - sum[l - 1][j] > 0) {
                    printf("%d\n", sum[r][j] - sum[l - 1][j]);
                    break;
                }
        }

    }
}