#include <iostream>
#include <vector>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++ t) {
        int n, q;
        cin >> n >> q;
        string s;
        cin >> s;
        vector<vector<int>> cnt(n, vector<int>(26, 0));
        ++ cnt[0][s[0] - 'A'];
        for (int i = 1; i < n; ++ i) {
            for (int j = 0; j < 26; ++ j) cnt[i][j] = cnt[i - 1][j];
            ++ cnt[i][s[i] - 'A'];
        }

        cout << "Case #" << t << ":\n";
        while (q -- > 0) {
            int l, r;
            cin >> l >> r;
            -- l, -- r;
            for (int i = 0; i < 26; ++ i) if (cnt[r][i] - (l == 0 ? 0 : cnt[l - 1][i])) {
                cout << (cnt[r][i] - (l == 0 ? 0 : cnt[l - 1][i])) << endl;
                break;
            }
        }
    }

    return 0;
}