#include<math.h> 
#include<stdio.h> 
int f[21]; 
long long d,a; 
void calc(long long l) 
{ 
int i,nr=0; 
long long prod=1; 
for(i=0;i<f[0];i++) 
 if((1<<i)&l)  
 { 
  nr++; 
  prod=prod*f[i+1];  
 } 
if(nr%2==1)  
d=d+a/prod; 
else
d=d-a/prod; 
} 
void pinex() 
{ 
int i;
long long ns;
ns=1<<f[0];
for(i=1;i<ns;i++) 
 calc(i);  
} 
int main() 
{ 
freopen("pinex.in","r",stdin); 
freopen("pinex.out","w",stdout); 
int m,i,j; 
long long b,c,p; 
scanf("%d",&m); 
for(i=1;i<=m;i++)     
{       
f[0]=0;                
scanf("%I64d%I64d",&a,&b); 
if(b%2==0)         
{        
f[1]=2;        
f[0]=1;  
while(b%2==0)             
{             
b=b/2;             
}       
} 
c=sqrt(b);       
p=3; 
while(p<=c)         
{     
if(b%p==0)             
{       
f[++f[0]]=p;      
while(b%p==0)             
{         
b=b/p;            
}            
}     
p=p+2;         
}      
if(b>1)             
f[++f[0]]=b;       
d=0;  
pinex(); 
printf("%lld\n",a-d);   
} 
return 0; 
}