# 题目分析

$\mu(m)=\sum_{m|d} F(d)$

$F(m)=\sum_{m|d} \mu(d) \mu(\frac{m}{d})$

$=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 [gcd(i,m)==1]$

$=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 \sum_{t|i,t|m} \mu(t)$

$=\mu(m)\sum_{t|m} \mu(t) \sum_{t|i}^{\lfloor \frac{n}{m} \rfloor} \mu(i)^2$

# 代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
typedef long long LL;
const int N=100000;
LL n,m;int T,js,tot,pri[35],is[N+5],p[N+5],mu[N+5];

void prework() {
int tot=0;mu[1]=1;
for(RI i=2;i<=N;++i) {
if(!is[i]) p[++tot]=i,mu[i]=-1;
for(RI j=1;j<=tot&&p[j]*i<=N;++j) {
is[p[j]*i]=1;
if(i%p[j]==0) break;
else mu[p[j]*i]=-mu[i];
}
}
}
LL dfs(int x,int now,int nowmu) {
if(x==js+1) {
LL re=0;
for(RI i=1;i*i<=n/m;++i) {
LL tmp=1LL*i*i/__gcd(i*i,now)*now;
re+=n/m/tmp*mu[i];
}
return re*nowmu;
}
return dfs(x+1,now,nowmu)+dfs(x+1,now*pri[x],-nowmu);
}
LL work() {
int km=m;js=0;
for(RI i=2;i*i<=km;++i) if(km%i==0) {
int c=0;
while(km%i==0) km/=i,++c;
if(c>1) return 0;
pri[++js]=i;
}
if(km!=1) pri[++js]=km;
return dfs(1,1,1)*((js&1)?-1:1);
}

int main()
{
scanf("%d",&T),prework();
while(T--) scanf("%lld%lld",&n,&m),printf("%lld\n",work());
return 0;
}


Orz!