#include <cstdio>#include <cstring>using namespace std;typedef long long LL;#define MAXN 100int fac[ MAXN ], cnt;void gaoji( int x )    //对x质因数分解 {    cnt = 0;    for( int i = 2; i * i <= x; )    {        if( x % i == 0 )        {                fac[ cnt++ ] = i;            while( x % i == 0) x /= i;        }        if( i == 2 ) i++;        else i += 2;    }    if( x > 1 )        fac[ cnt++ ] = x;}LL solve( LL x ){    LL res = 0;    for( LL i = 1; i < ( 1 << cnt ); ++i ) //二进制压缩     {        LL mul = 1, bits = 0;        for( LL j = 0; j < cnt; ++j )        {            if( ( i >> j ) & 1 )            {                ++bits;                mul *= fac[j];            }        }        if( bits & 1 )    res += x / mul;        else        res -= x / mul;    }    return x - res;} void Orz(){    int t, cas = 1, n;    scanf( "%d", &t );    while( t-- )    {        LL a, b;        scanf( "%I64d %I64d %d", &a, &b, &n );        gaoji( n );        LL ans = solve( b ) - solve( a - 1 );        printf( "Case #%d: %I64d\n", cas++, ans );    }}int main(){    Orz();        return 0;}