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

const int N = 100005;
char s[N];
int sum[N][26];

int main() {
  std::ios::sync_with_stdio(false);
  int T;
  std::cin >> T;
  for (int ca = 1; ca <= T; ++ ca) {
    int n, q;
    std::cin >> n >> q;
    std::cin >> s + 1;
    std::cout << "Case #" << ca << ":" << std::endl;
    for (int i = 1; s[i]; ++ i) {
      for (int j = 0; j < 26; ++ j) {
        sum[i][j] = sum[i - 1][j];
      }
      sum[i][s[i] - 'A'] ++;
    }
    while (q --) {
      int l, r;
      std::cin >> l >> r;
      for (int j = 0; j < 26; ++ j) {
        if (sum[r][j] - sum[l-1][j] > 0) {
          std::cout << sum[r][j] - sum[l-1][j] << std::endl;
          break;
        }
      }
    }
  }
  return 0;
}