# include <stdio.h>
# include <cstring>
# include <math.h>
# include <algorithm>

using namespace std;

int c[1000000],p[1000005],x,i,s,j,k,m,n;
bool viz[1000005];
long long a,b;
void submultimi()
{
	int i,q=1;
	long long suma=0;
	for (i=1; i<(1<<m); i++)
	{
		long long prod=1;
		long long x=i;
		int nr1=0;
		for (int j=0; j<m; j++)
			if (i & (1<<j)){
				prod =1LL * prod * c[j+1];
				nr1++;
			}
		if (nr1%2==1)
		{
			if (prod) suma+=a/prod;
		}
		else
			if (prod) suma-=a/prod;
	}
	printf("%lld\n",a-suma);
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d\n",&n);
	k=0;
	fill (viz +2 , viz + 1000005, true);
	p[++k]=2;
	for (i=3; i<=1000005; i+=2)
		if (viz[i]==false)
		{
			p[++k]=i;
			for (j=2*i; j<=1000005; j+=i)
				viz[j]=true;
		}
	for (s=1; s<=n; s++)
	{
		scanf("%lld %lld\n",&a,&b);
		m=0;
		memset(c,0,sizeof(c));
		x=b; i=1;
		while (x!=1)
		{
			i++;
			if (x%p[i]==0)
			{
				c[++m]=p[i];
				while (x%p[i]==0) x/=p[i];
			}
		    if (p[i] > sqrt(x) && x > 1) {
             c[++m] = x;
             x = 1;
		    }
		}
		submultimi();
	}
}