#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100000;
const int Q = 100000;

int sum[N + 1][26];

char str[N + 1];

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int n, q;
    scanf("%d %d", &n, &q);
    scanf("%s", str);
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) sum[i + 1][j] = sum[i][j];
      int ch = str[i] - 'A';
      sum[i + 1][ch]++;
    }
    int cnt = 0;
    for (int i = 0, l, r; i < q; i++) {
      scanf("%d %d", &l, &r);
      int odd = 0;
      for (int j = 0; j < 26; j++)
        if (((sum[r][j] - sum[l - 1][j]) & 1) != 0) odd++;
      if (odd <= 1) cnt++;
    }
    printf("Case #%d: %d\n", t, cnt);
  }
  return 0;
}