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

void solve(){
    string s, p;
    cin>>s>>p;
    int q;
    cin>>q;

    int n = s.length(), m = p.length();
    int pow = 31;
    int mod = 1e9 + 7;

    vector<long long> pp(n);
    pp[0] = 1;

    for(int i = 1; i < n; i++){
        pp[i] = (pp[i-1]*pow)%mod;
    }

    vector<long long> hs(n + 1);
    hs[0] = 0;

    for(int i = 0; i < n; i++){
        hs[i+1] = (hs[i] + (s[i] - 'a' + 1)*pp[i])%mod;
    }

    long long hp = 0;

    for(int i = 0; i < m; i++){
        hp = (hp + (p[i] - 'a' + 1)*pp[i])%mod;
    }

    while(q--){
        int a, b;
        cin>>a>>b;

        int i = a;
        int cnt = 0;
        
        while(i +  m <= b + 1){
            long long sstrh = (hs[i + m] - hs[i] + mod)%mod;
            long long tph = (hp * pp[i])%mod;
            if(tph == sstrh){
                cnt++;
                i += m;
            }
            else{
                i++;
            }
        }
        cout<<cnt<<endl;
    }
}

int main()
{
    long long t;
    cin >> t;
    for(int it=1;it<=t;it++) {
     cout << "Case " << it << ":"<<endl;
        solve();
    }
    return 0;
}