#include<stdio.h>
#include<math.h>
#define max 1000000
#define max2 79000


int a[max2],b[max2],t,nr,i,j,n,ok[max];
long long x,y,s;

void ciur()
{
	for (i=2;i<=max;i++)
		if (ok[i]==0)
			for (j=i*2;j<=max;j+=i)
				ok[j]=1;

	nr=0;		
	for (i=2;i<=max;i++)
		if (!ok[i])
		{
			nr++;
			a[nr]=i;
		}
}

void sum(int n)
{
	int i,k,nr2;
	long long p;
	
	for (i=1;i<=(1<<n)-1;i++)
	{
		nr2=0;
		k=i;
		p=1;	
		for (j=1;j<=n;j++)
		{
			if (k%2==1) 
				{
					nr2++;
					p*=b[j];
			}
			k/=2;
		}
		if (nr2%2) s+=(y/p);
			else s-=(y/p);
	}
}

void pinex()
{
	int i,q=0;

	for (i=1;i<=nr;i++)
		if (x%a[i]==0)
			{
			while (x%a[i]==0) x/=a[i];
			q++;
			b[q]=a[i];
			if (x==1) break;
		}
		
	if (x!=1)
	{
		q++;
		b[q]=x;
	}
		
	sum(q);		
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%d",&t);
	
	ciur();
	
	for (i=1;i<=t;i++)
	{
		scanf("%lld%lld",&y,&x);
		s=0;
		pinex();
		printf("%lld\n",y-s);
	}
	
	return 0;
}