#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll a,b,n;

 const int maxn=1e5+;

 ll fac[maxn];

 int cnt;

 void factor(ll n)

 {

     cnt=;

     for(int i=;i<maxn;i++)

     {

         if(n%i==)

         {

             fac[cnt++]=i;

         }

         while(n%i==)

         {

             n/=i;

         }

     }

     if(n>) fac[cnt++]=n;

 }

 ll solve(ll x)

 {

     ll que[maxn],k,t=;

     que[t++]=-;

     for(int i=;i<cnt;i++)

     {

         k=t;

         for(int j=;j<k;j++)

         {

             que[t++]=que[j]*fac[i]*(-);

         }

     }

     ll ans=;

     for(int i=;i<t;i++)

     {

         ans+=x/que[i];

     }

     return ans;

 }

 ll query(ll x)

 {

     return x-solve(x);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     int cas=;

     while(T--)

     {

         scanf("%I64d%I64d%I64d",&a,&b,&n);

         factor(n);

         ll ans=query(b)-query(a-);

         printf("Case #%d: %I64d\n",++cas,ans);

     }

     return ;

 }