#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b,nr,n,sol,i,d,t,k,j,v[300010],w[50010];
int f[1000010],f1[50010],x[50010];
void bkt(int pas){
sol=1;
if(pas>1){
if((pas-1)%2==1){
for(i=1;i<pas;i++)
sol*=w[x[i]];
nr-=(a/sol);
}else{
for(i=1;i<pas;i++)
sol*=w[x[i]];
nr+=(a/sol);
}
}
for(int i=x[pas-1]+1;i<=n;i++)
if(f1[i]==0){
f1[i]=1;
x[pas]=i;
bkt(pas+1);
f1[i]=0;
}
}
int main(){
for(i=2;i<=1000000;i++)
if(f[i]==0){
v[++k]=i;
for(j=i*2;j<=1000000;j+=i)
f[j]=1;
}
fin>>t;
for(;t--;){
fin>>a>>b;
n=0;
d=1;
while(v[d]<=b/v[d]&&b!=1&&d<=k){
if(b%v[d]==0){
w[++n]=v[d];
while(b%v[d]==0)
b/=v[d];
}
d++;
}
if(b!=1)
w[++n]=b;
nr=a;
bkt(1);
fout<<nr<<"\n";
}
return 0;
}