#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
const int INF=0x3f3f3f3f;
typedef long long LL;
vector<int>p;
void getp(LL x){
	p.clear();
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			p.push_back(i);
			while(x%i==0)x/=i;
		}
	}
	if(x>1)p.push_back(x);
} 
LL tc(LL x){
	LL sum=0;
	for(int i=1;i<(1<<p.size());i++){
		LL num=0,cur=1;
		for(int j=0;j<p.size();j++){
			if(i&(1<<j)){
				num++;
				cur*=p[j];
			}
		}
		if(num&1)sum+=x/cur;
		else sum-=x/cur;
	}
	return x-sum;
}
int main(){
	LL T,A,B,K,flot=0;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&A,&B,&K);
		getp(K);
		printf("Case #%lld: %lld\n",++flot,tc(B)-tc(A-1));
	}
	return 0;
}