1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define LL __int64 5 using namespace std; 6  7 int t; 8 LL a,b,n; 9 LL f[1000];10 int cnt;11 12 void inti()13 {14     memset(f,0,sizeof(f));15     cnt=0;16     for(int i=2; i*i<=n; i++)17     {18         if(n%i==0)19         {20            f[cnt++]=i;21            while(n%i==0)22            {23                n=n/i;24            }25         }26     }27     if(n>1)28     {29         f[cnt++]=n;30     }31 }32 33 LL Get_num(LL m)34 {35     LL ans=0;36     for(int i=1; i<(1<<cnt); i++)37     {38         int xx=0;39         LL x=1;40         for(int j=0; j<cnt; j++)41         {42             if(i&(1<<j))43             {44                xx++;45                x*=f[j];46             }47         }48         if(xx%2!=0)49         {50             ans+=m/x;51         }52         else53         {54             ans-=m/x;55         }56     }57     return m-ans;58 }59 60 int main()61 {62     scanf("%d",&t);63     for(int cas=1; cas<=t; cas++)64     {65         scanf("%I64d%I64d%I64d",&a,&b,&n);66         inti();67         printf("Case #%d: %I64d\n",cas,Get_num(b)-Get_num(a-1));68     }69     return 0;70 }