#include <fstream>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int dim=1e6;
int t,nrp[100000],d[100],p;
long long a,b,s,val;
bool ciur[dim+2];
void back(int k,int last){
if(k==d[0]+1){
if(d[0]%2==0)
s-=a/val;
else
s+=a/val;
}else{
if(k!=1){
if((k-1)%2==0)
s-=a/val;
else
s+=a/val;
}
for(int i=last+1;i<=d[0];i++){
val*=d[i];
back(k+1,i);
val/=d[i];
}
}
}
int main()
{
ciur[0]=ciur[1]=1;
for(int i=2;i<=dim;i++)
if(ciur[i]==0){
nrp[++p]=i;
for(int j=2*i;j<=dim;j+=i)
ciur[j]=1;
}
cin>>t;
while(t--){
cin>>a>>b;
d[0]=0;
if(b==1){
cout<<a<<'\n';
continue;
}
for(int i=1;i<=p&&1LL*nrp[i]*nrp[i]<=b;i++)
if(b%nrp[i]==0){
d[++d[0]]=nrp[i];
while(b%nrp[i]==0)
b/=nrp[i];
}
if(b!=1)
d[++d[0]]=b;
s=0;
val=1;
back(1,0);
cout<<a-s<<'\n';
}
return 0;
}