#include<stdio.h>
#include<math.h>
unsigned long long int ara1[5000010];
int main ()
{
    int i,j,test,c,a,b,n,e,v;
    int ara2[10000];
    unsigned long long int result;
    double x,y;
    int ara3[10000];
    for(i=0; i<10000; i++)
    {
        ara2[i]=1;
        ara3[i]=0;
    }
    for(i=2; i<=100; i++)
    {
        for(j=2; j*i<=2500; j++)
        {
            ara2[i*j]=0;
        }
    }
    ara3[0]=2;
    c=1;
    for(i=3; i<=10000; i++)
    {
        if(ara2[i]==1)
        {
            ara3[c]=i;
            c++;
        }
    }

    for(i=1; i<=5000000; i++)
    {
        ara1[i]=i;
        n=sqrt(i);
        v=i;
        for(j=0; j<c && ara3[j]<=n; j++)
        {
            if(v%ara3[j]==0)
            {
                x=(1/(1.00*ara3[j]));
                x=1-x;
                y=ara1[i]*1.00;
                y=y*x;
                ara1[i]=1*y;
                while(v%ara3[j]==0)
                {
                    v=v/ara3[j];
                }
            }
        }
        if(v!=1)
        {
            x=(1/(1.00*v));
            x=1-x;
            y=ara1[i]*1.00;
            y=y*x;
            ara1[i]=1*y;
        }
        ara1[i]=ara1[i]*ara1[i];
    }
    ara1[1]=0;
    for(i=2; i<=5000000; i++)
    {
        ara1[i]=ara1[i];
        ara1[i]=ara1[i]+ara1[i-1];
    }
    scanf("%d",&test);
    for(i=0; i<test; i++)
    {
        scanf("%d %d",&a,&b);
        result=ara1[b]-ara1[a-1];
        printf("Case %d: %llu\n",i+1,result);
    }
    return 0;
}