#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MAX 320000
bool mark[MAX+5];
vector<ll>isprime;

void sieve()
{
    ll i,j;
    mark[0]=true;
    mark[1]=true;
    for(i=2;i*i<=MAX;i++)
    {
        if(mark[i]==false)
        {
            for(j=i*i;j<=MAX;j+=i)
                mark[j]=true;
        }
    }
    for(i=2;i<=MAX;i++)
        if(mark[i]==false)
        isprime.push_back(i);
}


void segsieve(ll l,ll r)
{
    ll prime[r-l+1+5],i,j;
    for(i=0;i<r-l+1;i++)
        prime[i]=false;
    if(l==1)prime[0]=true;
    for(i=0;isprime[i]*isprime[i]<=r;i++)
    {
        ll curprime=isprime[i];
        ll base=(l/curprime)*curprime;
        if(base<l)
            base+=curprime;
        for(j=base;j<=r;j+=curprime)
        {
            prime[j-l]=true;
        }
        if(base==curprime)
           prime[base-l]=false;
    }
    vector<ll>v;
    for(i=0;i<r-l+1;i++){
        if(prime[i]==false){
          v.push_back(i+l);
        }
    }
    cout<<v.size()<<endl;
    return;
}

int main()
{
    sieve();
    ll t,i,j,k,l,r;
    cin>>t;
    for(ll cas=1;cas<=t;cas++)
    {
        cin>>l>>r;
        cout<<"Case "<<cas<<": ";
        segsieve(l,r);
    }
    return 0;
}