#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll N=1e6;
ll ans[N*5+9];
int prime[N+9];
ll phii[N*5+9];

void init()
{
    for(ll i=1; i<=N; i++)
        ans[i]=i;
}

void setval(ll n)
{
    for(ll i=n; i<=N; i+=n)
    {
        ans[i]/=n;
        ans[i]*=n-1;
    }
}

void phi()
{
    setval(2);
    for(ll j=3; j*j<=N; j+=2)
    {
        if(prime[j]==0)
        {
            setval(j);
            for(ll i=j*j; i<=N; i+=j)
                prime[i]=1;
        }
    }
}
void solve()
{
    for(ll i=2; i<=N; i++)
    {
        phii[i]=phii[i-1]+(ans[i]*ans[i]);
    }
}

int main()
{
    init();
    phi();
    solve();
    ll test;
    scanf("%llu",&test);
    for(ll i=1; i<=test; i++)
    {
        ll a,b;
        scanf("%llu %llu",&a,&b);
        a--;
        printf("Case %llu: %llu\n",i,phii[b]-phii[a]);
    }
}