//#include<fstream.h>
//ifstream f("pinex.in"); ofstream g("pinex.out");
#include<stdio.h>
char ciur[1000005]; //ciur[i] == 0 daca i este prim
long long a,b,sum,s,pr,p[100001],d[30];
int T,i,j,n,nr=0,m,k,x[30];
void prelsol()
{long long pr=1;
 for(int i=1; i<=n; i++) pr=pr*d[x[i]];
 s+=a/pr;
}
void back()
{s=0; pr=1; k=1; x[k]=0;
 do {while(x[k]<m-n+k)
		{x[k]++;
		 pr*=d[x[k]];
		 if(k==n) 
		    {s+=a/pr;
    		 pr/=d[x[k]];
			}// prelsol(); 
		  else {k++; x[k]=x[k-1];};
		}
	 k--;
	if(k)pr/=d[x[k]]; 
	}
 while(k); 
 if(n%2) sum+=s; else sum-=s;
} 
int main()
{freopen("pinex.in","r",stdin);
 freopen("pinex.out","w",stdout);
	for(i=2; i<=500000; i++)
  if(!ciur[i])
   {p[++nr]=i;
	for(j=i+i; j<=1000000; j+=i) ciur[j]=1;
   };
// f>>T;
 scanf("%ld",&T);
 while(T)  
   {//f>>a>>b;
	scanf("%lld%lld",&a,&b);
	m=0; i=1;
    while(b>1 && p[i]*p[i]<=b)
	  {if(b%p[i]==0)
		  {d[++m]=p[i];
		   while(b%p[i]==0) b/=p[i];
		  };
		i++;
	  }
	if(b>1) d[++m]=b;
	sum=0; 
	for(n=1; n<=m; n++)
		back();
	//g<<a-sum<<'\n';  
	printf("%lld\n",a-sum);
	T--;
   }
 //g.close(); 
 return 0;
}
/*
#include<stdio.h>
#include<math.h>
long long a;
long long b;
bool c[1000011];
long p[800011];
long e[800011];    
void desc ()
{
	long lim,d,ex=0,num=1,n,ns,v,bi,w=0,nb,i;
	long long prod=1,s=0;
	lim=sqrt(b);
	n=b;
	d=2;num=1;
	while (d<=lim && b>1)
	{
		ex=0;
		while (b%d==0)
		{
			b=b/d;
			ex++;
		}
		if (ex)
			e[++w]=d;
		num++;
		d=p[num];
	}
	if (b>1)
		e[++w]=b;
	ns=(1<<w)-1;
	for (v=1;v<=ns;v++)
		{
			prod=1;nb=0;
			for (bi=0;bi<w;bi++)
				if (v&(1<<bi))
				{
					prod=(long long)prod*e[w-bi];
					nb++;
				}
			if (nb&1)
				s=(long long)s+a/prod;
			else
				s=(long long)s-a/prod;
		}
	printf("%lld\n",a-s);
}

void ciur()
{
	long i,j;
	c[1]=1;
	p[1]=2;
	p[0]=1;
	for (i=2;i<=1000010;i=i+2)
		c[i]=1;
	for (i=3;i<=1000010;i=i+2)
	{
		if (!c[i])
	{
		p[++p[0]]=i;
		for (j=i+i+i;j<=1000010;j=j+(i<<1))
			c[j]=1;
	}
	}
}

int main()
{
	long m,i;
	
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%ld",&m);
	ciur();
	for (i=1;i<=m;i++)
	{
		scanf("%lld%lld",&a,&b);
		desc();
	}	
	return 0;
}
*/