#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;

int t, n, q, l, r;
string s;
int vis[100005][30];

int main()
{
    scanf("%d", &t);
    for(int z = 1; z <= t; ++z)
    {
        scanf("%d %d", &n, &q);
        cin >> s;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 'A'; j <= 'Z'; ++j)
            {
                if(j == s[i - 1])
                    vis[i][j - 'A'] = vis[i - 1][j - 'A'] + 1;
                else vis[i][j - 'A'] = vis[i - 1][j - 'A'];
            }
        }
        printf("Case #%d:\n", z);
        while(q--)
        {
            scanf("%d %d", &l, &r);
            int ans = 0;
            for(int j = 'Z'; j >= 'A'; --j)
                if(vis[r][j - 'A'] - vis[l - 1][j - 'A'] > 0)
                    ans = vis[r][j - 'A'] - vis[l - 1][j - 'A'];
            printf("%d\n", ans);
        }
    }
}