#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

void calc()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    vector<int> pos[26];

    for (int i = 0; i < 26; ++i) {
        pos[i].reserve(n);
    }

    for (int i = 0; i < n; ++i) {
        pos[s[i] - 'A'].push_back(i);
    }

    vector<int> res;

    string line;
    getline(cin, line);
    int l, r;
    while (q--) {
        getline(cin, line);

        l = 0;
        int i = 0;
        for (; i < line.length(); ++i) {
            if (line[i] == ' ') break;
            l *= 10;
            l += line[i] - '0';
        }

        ++i;
        r = 0;
        for (; i < line.length(); ++i) {
            r *= 10;
            r += line[i] - '0';
        }

        // cin >> l >> r;
        --l;
        --r;

        for (int i = 0; i < 26; ++i) {
            vector<int>::iterator low = lower_bound(pos[i].begin(), pos[i].end(), l);
            vector<int>::iterator up = upper_bound(low, pos[i].end(), r);
            if (up > low) {
                res.push_back(up - low);
                break;
            }
        }
        // res.push_back(r - l);
    }

    std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout, "\n"));
}

int main(void)
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i) {
        cout << "Case #" << i << ":" << endl;
        calc();
    }
}