#include <bits/stdc++.h>
using namespace std;
vector <int> vec(100000020);
vector <int> prime;
void sieve()
{
vec[0]=1;
vec[1]=1;
for(int i=2;i<=sqrt(100000020);i++){
if(vec[i]==0){
prime.push_back(i);
for(int j=2;j*i<=100000020;j++){
vec[j*i]=1;
}
}
}
}
int main()
{
int t;
cin >> t;
sieve();
for(int i=1;i<=t;i++){
int l,u,pos2,pos1;
cin >> l >> u;
vector <int> ::iterator it1;
vector <int> ::iterator it2;
it1=lower_bound(prime.begin(),prime.end(),l);
it2=lower_bound(prime.begin(),prime.end(),u);
if(u==0 || u==1){
pos2=0;
}
else if(*it2!=u){
pos2=it2-prime.begin()-1;
}
else{
pos2=it2-prime.begin()+1;
}
if(l==0 || l==1){
pos1=0;
}
else{
pos1=it1-prime.begin();
}
printf("Case %d: %d\n",i,pos2-pos1);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvciA8aW50PiB2ZWMoMTAwMDAwMDIwKTsKdmVjdG9yIDxpbnQ+IHByaW1lOwp2b2lkIHNpZXZlKCkKewogICAgdmVjWzBdPTE7CiAgICB2ZWNbMV09MTsKICAgIGZvcihpbnQgaT0yO2k8PXNxcnQoMTAwMDAwMDIwKTtpKyspewogICAgICAgIGlmKHZlY1tpXT09MCl7CiAgICAgICAgICAgIHByaW1lLnB1c2hfYmFjayhpKTsKICAgICAgICAgICAgZm9yKGludCBqPTI7aippPD0xMDAwMDAwMjA7aisrKXsKICAgICAgICAgICAgICAgIHZlY1tqKmldPTE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgc2lldmUoKTsKICAgIGZvcihpbnQgaT0xO2k8PXQ7aSsrKXsKICAgICAgICBpbnQgbCx1LHBvczIscG9zMTsKICAgICAgICBjaW4gPj4gbCA+PiB1OwogICAgICAgIHZlY3RvciA8aW50PiA6Oml0ZXJhdG9yIGl0MTsKICAgICAgICB2ZWN0b3IgPGludD4gOjppdGVyYXRvciBpdDI7CiAgICAgICAgaXQxPWxvd2VyX2JvdW5kKHByaW1lLmJlZ2luKCkscHJpbWUuZW5kKCksbCk7CiAgICAgICAgaXQyPWxvd2VyX2JvdW5kKHByaW1lLmJlZ2luKCkscHJpbWUuZW5kKCksdSk7CiAgICAgICAgaWYodT09MCB8fCB1PT0xKXsKICAgICAgICAgICAgcG9zMj0wOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKCppdDIhPXUpewogICAgICAgICAgICBwb3MyPWl0Mi1wcmltZS5iZWdpbigpLTE7CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIHBvczI9aXQyLXByaW1lLmJlZ2luKCkrMTsKICAgICAgICB9CiAgICAgICAgaWYobD09MCB8fCBsPT0xKXsKICAgICAgICAgICAgcG9zMT0wOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBwb3MxPWl0MS1wcmltZS5iZWdpbigpOwogICAgICAgIH0KICAgICAgICBwcmludGYoIkNhc2UgJWQ6ICVkXG4iLGkscG9zMi1wb3MxKTsKICAgIH0KfQ==