/*************************************************************************
    > File Name: fhc.cpp
    > Author: Toka
    > Created Time: 2018年07月22日 星期日 23时31分24秒
 ************************************************************************/
// #pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#define MAXN 200003
#define MODP 1000000007
#define FST first
#define SCD second
using namespace std;
typedef long long LL;
typedef pair<int, int> PA;


char s[MAXN];
int cn[30][MAXN];

int main() {
    // int size = 256 << 20; // 256MB  
    // char *p = (char*)malloc(size) + size;  
    // __asm__("movl %0, %%esp\n" :: "r"(p));
    // freopen("in.txt", "r", stdin);
    int Tn = 1;
    scanf("%d", &Tn);
    for (int Ti = 1; Ti <= Tn; ++Ti) {
        int n,m;
        scanf("%d%d", &n, &m);
        scanf("%s", s);
        memset(cn, 0, sizeof(cn));
        int l = strlen(s);
        for (int i=0;i<l;++i) {
            for (int c='A';c<='Z';++c) {
                cn[c-'A'][i+1] = cn[c-'A'][i]+(s[i]==c);
            }
        }
        printf("Case #%d:\n", Ti);
        for (int i=0;i<m;++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            int mx = -1;
            for (int c='A';c<='Z';++c) {
                int cnt = cn[c-'A'][y] - cn[c-'A'][x-1];
                mx = max(mx, cnt);
                if (mx>0) break;
            }
            int ans = mx;
            printf("%d\n", ans);
        }
    }
    return 0;
}