#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for (int cas = 1; cas <= t; cas++) {
        cout << "Case #" << cas << ":\n";
        int n, q;
        string s;
        cin >> n >> q;
        cin >> s;
        vector< vector<int> > st(n + 1, vector<int>(26, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                st[i][j] = st[i - 1][j];
            }
            st[i][s[i - 1] - 'A'] ++;
        }
        while (q--) {
            int l, r;
            scanf("%d %d", &l, &r);
            for (int i = 0; i < 26; i++) {
                if (st[r][i] - st[l - 1][i] > 0) {
                    printf("%d\n", st[r][i] - st[l - 1][i]);
                    break;
                }
            }
        }

    }
    return 0;
}