#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64#define Np 100000using namespace std;bool isprime[Np];LL prime[Np],np;LL fac[100],fp;void initial(){	np=0;	memset(isprime,true,sizeof(isprime));	for(LL i=2;i<Np;i++){		if(isprime[i]){			prime[np++]=(LL)i;			for(LL j=i*i;j<Np;j+=i)			isprime[j]=false;		}	}}void dfs(LL i,LL num, LL p,LL s,LL &ans,LL n){	if(i>=n){		if(num==0){			ans=s;		}		else if(num&1){			ans-=s/p;		}		else ans+=s/p;		return ;	}	dfs(i+1,num,p,s,ans,n);	dfs(i+1,num+1,p*fac[i],s,ans,n);}LL  work(LL a,LL b,LL n){	LL p=n;	fp=0;	for(LL i=0;i<np&&prime[i]*prime[i]<=p;i++){		if(p%prime[i]==0){			fac[fp++]=prime[i];			while(p%prime[i]==0)			p/=prime[i];		}	}	if(p>1) fac[fp++]=p;		LL ansA,ansB;	ansA=ansB=0;		dfs(0,0,1,a-1,ansA,fp);	dfs(0,0,1,b,ansB,fp);		return ansB-ansA;}int main(){	int T,kase=0; 	LL a,b,n;	initial();	scanf("%d",&T);	while(T--){		scanf("%I64d%I64d%I64d",&a,&b,&n);		LL ans=work(a,b,n);		printf("Case #%d: %I64d\n",++kase,ans);	}	return 0;}