#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;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgc29sdmUoKXsKICAgIHN0cmluZyBzLCBwOwogICAgY2luPj5zPj5wOwogICAgaW50IHE7CiAgICBjaW4+PnE7CgogICAgaW50IG4gPSBzLmxlbmd0aCgpLCBtID0gcC5sZW5ndGgoKTsKICAgIGludCBwb3cgPSAzMTsKICAgIGludCBtb2QgPSAxZTkgKyA3OwoKICAgIHZlY3Rvcjxsb25nIGxvbmc+IHBwKG4pOwogICAgcHBbMF0gPSAxOwoKICAgIGZvcihpbnQgaSA9IDE7IGkgPCBuOyBpKyspewogICAgICAgIHBwW2ldID0gKHBwW2ktMV0qcG93KSVtb2Q7CiAgICB9CgogICAgdmVjdG9yPGxvbmcgbG9uZz4gaHMobiArIDEpOwogICAgaHNbMF0gPSAwOwoKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewogICAgICAgIGhzW2krMV0gPSAoaHNbaV0gKyAoc1tpXSAtICdhJyArIDEpKnBwW2ldKSVtb2Q7CiAgICB9CgogICAgbG9uZyBsb25nIGhwID0gMDsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKICAgICAgICBocCA9IChocCArIChwW2ldIC0gJ2EnICsgMSkqcHBbaV0pJW1vZDsKICAgIH0KCiAgICB3aGlsZShxLS0pewogICAgICAgIGludCBhLCBiOwogICAgICAgIGNpbj4+YT4+YjsKCiAgICAgICAgaW50IGkgPSBhOwogICAgICAgIGludCBjbnQgPSAwOwogICAgICAgIAogICAgICAgIHdoaWxlKGkgKyAgbSA8PSBiICsgMSl7CiAgICAgICAgICAgIGxvbmcgbG9uZyBzc3RyaCA9IChoc1tpICsgbV0gLSBoc1tpXSArIG1vZCklbW9kOwogICAgICAgICAgICBsb25nIGxvbmcgdHBoID0gKGhwICogcHBbaV0pJW1vZDsKICAgICAgICAgICAgaWYodHBoID09IHNzdHJoKXsKICAgICAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgICAgICAgaSArPSBtOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dDw8Y250PDxlbmRsOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIGxvbmcgbG9uZyB0OwogICAgY2luID4+IHQ7CiAgICBmb3IoaW50IGl0PTE7aXQ8PXQ7aXQrKykgewogICAgIGNvdXQgPDwgIkNhc2UgIiA8PCBpdCA8PCAiOiI8PGVuZGw7CiAgICAgICAgc29sdmUoKTsKICAgIH0KICAgIHJldHVybiAwOwp9CgoK