#include <iostream>
using namespace std;
#define maxn 70
long long  prime[maxn];
long long  getans(long long num,int m)　　　　　　　　//求1-mun  不互素的数，m为num素因子的个数；
{　　　　　　　　　　　　　　　　　　　　　　　　　　　//利用容斥原理
    long long  ans=0,tmp,i,j,flag;
    for(i=1;i<(long long)(1<<m);i++){
        tmp=1,flag=0;
        for(j=0;j<m;j++)
            if(i&((long long)(1<<j)))
                flag++,tmp*=prime[j];
        if(flag&1)
            ans+=num/tmp;
        else
            ans-=num/tmp;
    }
    return ans;
}
int main()
{
    int T,t=0,m;
    long long  n,a,b;
    cin>>T;
    while(T--){
        cin>>a>>b>>n;
        m=0;
        for(int i=2;i*i<n;i++){
            if(n&&n%i==0){
                prime[m++]=i;
                while(n&&n%i==0)
                    n/=i;
            }
        }
        if(n>1)prime[m++]=n;
        cout<<"Case #"<<++t<<": "<<(b-getans(b,m))-(a-1-getans(a-1,m))<<endl;

    }
    return 0;
}