#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;

int n;
char s[MAXN+1];

int prefix[26][MAXN+1];

vector<int> getCnt(int start, int end) {
    vector<int> ans(26, 0);
    for(int i=0; i<26; i++) {
        ans[i] = prefix[i][end] - prefix[i][start];
    }
    return ans;
}

bool isValid(int a, int b, int c, int d) {
    vector<int> cntLeft = getCnt(a, b);
    vector<int> cntRight = getCnt(c, d);
    bool valid = true;
    int diffByOne = 0;
    for(int i=0; i<26; i++) {
        if(cntLeft[i] == cntRight[i]) {
        }
        else if(cntLeft[i] + 1 == cntRight[i]) {
            diffByOne++;
        }
        else {
            valid = false;
        }
    }
    if(valid and diffByOne == 1) {
        return true;
    }
    return false;
}

int solve() {
    scanf("%s", s);
    n = strlen(s);

    for(int i=0; i<26; i++) {
        for(int j=0; j<n; j++) {
            prefix[i][j+1] = prefix[i][j] + (s[j] == ('a' + i));
        }
    }

    int q;
    scanf("%d", &q);

    int ans = 0;
    while(q--) {
        int left, right;
        scanf("%d %d", &left, &right);

        left--;
        int len = right - left;
        int mid = left + len / 2;
        if(len % 2 == 0) {
            continue;
        }
        if(len == 1) {
            ans++;
            continue;
        }

        if(isValid(left, mid, mid, right)) {
            ans++;
        }
        else if(isValid(mid+1, right, left, mid+1)) {
            ans++;
        }
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    for(int test=1; test<=t; test++) {
        printf("Case #%d: %d\n", test, solve());
    }
}