#include<math.h> 
#include<stdio.h> 
long long f[21];
const long g=1000000;
bool o[1000001];
long long np[80000];
long long d,a; 
void ciur()
{
long i,j;	
for(i=4;i<=g;i=i+2)
	o[i]=1;
np[0]=1;
np[1]=2;
for(i=3;i<=g;i=i+2)
{
	if(o[i]==0)
	{
		for(j=i+i+i;j<=g;j=j+i+i)
			o[j]=1;
		np[0]++;
		np[np[0]]=i;
	}	
}
}
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; 
scanf("%d",&m); 
for(i=1;i<=m;i++)     
{       
f[0]=0;                
scanf("%lld%lld",&a,&b); 
if(b%2==0)         
{        
f[1]=2;        
f[0]=1;  
while(b%2==0)             
{             
b=b/2;             
}       
} 
ciur();
c=sqrt(b);
for(j=2;np[j]<=c&&b>1;j++)
	if(b%np[j]==0)
	{
		while(b%np[j]==0)
		{
			b=b/np[j];
		}
	f[0]++;	
	f[f[0]]=np[j];
	}
if(b>1)             
	{
	f[0]++;	
	f[f[0]]=b;       
	}
d=0;  
pinex(); 
printf("%lld\n",a-d);   
} 
return 0; 
}