思路：直接用求(b,1)范围内互质的数，(a-1,1)范围内互质的数。再求反
就是敲一下容斥模板
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=;
#define LL long long
// inline int r(){
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
// } int T;
LL a,b,n;
int pri[];
int k;
void fun(LL x){
k=;
for(int i=;i*i<=x;i++){
if(x&&x%i==){
pri[k++]=i;
while(x&&x%i==){
x/=i;
}
}
}
if(x>) pri[k++]=x;
}
LL exclu(LL num,int m){
LL ans=,tmp,times;
for(int i=;i<(LL)(<<m);i++){
tmp=,times=;
for(int j=;j<m;j++){
if(i&((LL)(<<j)))
times++,tmp*=pri[j];
}
if(times&) ans+=num/tmp;
else ans-=num/tmp;
}
return ans;
}
int main(){
scanf("%d",&T); int cas=;
while(T--){
scanf("%I64d%I64d%I64d",&a,&b,&n);
clc(pri,);
fun(n);
LL ans1=exclu(a-,k);
LL ans2=exclu(b,k);
printf("Case #%d: %I64d\n",cas++,b-ans2-(a--ans1));
}
return ;
}