#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

typedef __int64 ll;

ll A,B,N;

vector <ll> v;

ll gao(ll n){

    int m=v.size();

    ll res=;

    for(int i=;i<(<<m);i++){

        int cnt=;

        ll temp=;

        for(int j=;j<m;j++){

            if(i&(<<j)){

                cnt++;

                temp*=v[j];

            }

        }

        if(cnt&)res+=n/temp;

        else res-=n/temp;

    }

    return n-res;

}

int main(){

    int T;

    scanf("%d",&T);

    for(int cas=;cas<=T;cas++){

        scanf("%I64d%I64d%I64d",&A,&B,&N);

        v.clear();

        for(ll i=;i*i<=N;i++){

            if(N%i==){

                v.push_back(i);

                while(N%i==)N/=i;

            }

        }

        if(N>)v.push_back(N);

        printf("Case #%d: %I64d\n",cas,gao(B)-gao(A-));

    }

    return ;

}