#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l+r)>>1)
#define fst first
#define snd second
#define sfn scanf("%d",&n)
#define sfnm scanf("%d%d",&n,&m)
#define sft scanf("%d",&t)
#define pfans printf("%d\n",ans)
using namespace std;
typedef long long lint;

lint a,b,n,t;
vector<lint> sushu;

void getFac(lint n){    //求n的所有素因数
    sushu.clear();
    for(int i = 2; i * i <= n; ++i){
        if(n % i == 0){
            sushu.push_back(i);
            while(n % i == 0){ n /= i;}
        }
    }
    if(n > 1){
        sushu.push_back(n);
    }
}

lint getNum(lint n){    //求1-n有多少数字和k不互素
    lint len = 1 << sushu.size();
    lint re = 0;
    if(n == 0){ return 0;}
    for(int i = 1; i < len; ++i){
        lint sum = 0;
        lint now = 1;
        for(int j = 0; j < sushu.size(); ++j){
            if((1<<(j))&i){
                ++sum; now *= sushu[j];
            }
        }
        sum&1?re+=n/now:re-=n/now;
    }
    return re;
}

int main(){
    scanf("%I64d",&t);
    int ca = 0;
    while(t--){
        ++ca;
        scanf("%I64d%I64d%I64d",&a,&b,&n);
        getFac(n);
        lint ansa = a - 1 - getNum(a - 1);
        lint ansb = b - getNum(b);
        lint ans = ansb - ansa;
        printf("Case #%d: %I64d\n",ca,ans);
    }
    return 0;
}