#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define INF 0X3F3F3F3F
#define N 200005
#define M 200005
#define LL long long
#define ULL unsigned long long
#define FF(i, a, b) for(int i = a; i <= b; ++i)
#define RR(i, a, b) for(int i = a; i >= b; --i)
#define FJ(i, a, b) for(int i = a; i < b; ++i)
#define SC(x) scanf("%d", &x)
#define SCC(x, y) scanf("%d%d", &x, &y)
#define SCCC(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define SS(x) scanf("%s", x)
#define PR(x) printf("%d\n", x)
#define PII pair<int, int>
#define PLL pair<unsigned long long, unsigned long long>
#define MP make_pair
#define PB push_back
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
using namespace std;
inline void II(int &n){char ch = getchar(); n = 0; bool t = 0;
for(; ch < '0'; ch = getchar()) if(ch == '-') t = 1;
for(; ch >= '0'; n = n * 10 + ch - '0', ch = getchar()); if(t) n =- n;}
inline void OO(int a){if(a < 0) {putchar('-'); a = -a;}
if(a >= 10) OO(a / 10); putchar(a % 10 + '0');}
const long double eps = 1e-8;
int sgn(long double x){
    return (x > eps) - (x < -eps);
}
int n, q, l, r;
char str[N];
int a[N][26];
int main(){
  //  IN;
    int _; SC(_);
    FF(CA, 1, _){
        int ans = 0;
        SCC(n, q);
        SS(str + 1);
        FF(i, 1, n){
            int t = str[i] - 'A';
            memcpy(a + i, a + i - 1, 26 * 4);
            ++a[i][t];
        }
        printf("Case #%d:\n", CA);
        FF(i, 1, q){
            SCC(l, r);
            for(int j = 0; j < 26; ++j){
                if(a[r][j] - a[l - 1][j] > 0){
                    printf("%d\n", a[r][j] - a[l - 1][j]);
                    break;
                }
            }
        }
    }

    return 0;
}