#include<stdio.h>
#define N 1000001
long long v[N],p[N],a[101],i,j,o,x,y,m,d,l,k,t,r,s;
int main()
{
	freopen("pinex.in","r",stdin),freopen("pinex.out","w",stdout);
	for(m=N-1,i=2,scanf("%lld",&o);i<=m;++i)
		if(!v[i])
			for(p[++d]=i,j=i*i;j<=m;j+=i)
				v[j]=1;
	while(o--) {
		for(scanf("%lld%lld",&x,&y),l=x,k=0,i=1;i*i<=y;++i)
			if(y%p[i]==0)
				for(a[++k]=p[i];y%p[i]==0;y/=p[i]);
		if(y>1)
			a[++k]=y;
		for(t=1<<k,i=1;i<t;++i) {
			for(r=1,s=j=0;j<k;++j)
				if((i&(1<<j))>0)
					s++,r*=a[j+1];
            l+=((s%2==0?1:-1)*x/r);
		}
		printf("%lld\n",l);
	}
	return 0;
}