#include<stdio.h>
int n,i,j,np,p[1000013],d[100],nd,q,nr;
long long a,b,x,y,z;
bool k[1000013];
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d",&n);
	for(i=2;i<=1000000;++i)k[i]=1;
    i=2;
    while(i*i<=1000000)
    {
        if(k[i])
        {
            j=i;
            while(i*j<=1000000)
            {
                k[i*j]=0;
                ++j;
            }
			p[np++]=i;
        }
        ++i;
    }
	for(int w=0;w<n;++w)
	{
		scanf("%lld%lld",&a,&b);
		i=0;
		nd=0;
		while(b!=1)
		{
			if(b%p[i]==0)
			{
				while(b%p[i]==0)b/=p[i];
				d[nd++]=p[i];
			}
			++i;
		}
		q=(long long)1<<nd;
		z=0;
		for(i=1;i<q;++i)
		{
			x=1;
			nr=0;
			for(j=0;j<nd;++j)
				if(i & ((long long)1<<j)) x*=d[j],++nr;
			if(nr%2==0)x=-x;
			z+=(a/x);
		}
		printf("%lld\n",a-z);
	}
	return 0;
}