#include <stdio.h>
#include <bitset>
#define ll long long
#define LMAX 1000005
#define HMAX 17
using namespace std;
bitset <LMAX> marc;
int n,A[LMAX],r,t,nrb;
ll a,b,nr[HMAX],act,rez;
void precompute()
{
	int i,j;
	for (i=2; i*i<LMAX; i++)
		if (!marc[i])
			for (j=i*i; j<LMAX; j+=i)
				marc[j]=1;
	for (i=2; i<LMAX; i++)
		if (!marc[i])
			A[++r]=i;
}
void desc()
{
	t=0; 
	int i;
	for (i=1; (ll)A[i]*A[i]<=b; i++)
		if (b % A[i]==0)
		{
			nr[++t]=A[i];
			while (b % A[i]==0)
				b/=A[i];
		}
	if (b!=1)
		nr[++t]=b;
}
void back(int k)
{
	if (k==t+1)
	{
		if (act!=1)
		{
			if (nrb & 1)
				rez+=a/act;
			else
				rez-=a/act;
		}
		return ;
	}
	act*=nr[k]; nrb++;
	back(k+1);
	act/=nr[k]; nrb--;
	back(k+1);
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	precompute();
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%lld%lld",&a,&b);
		desc();
		nrb=0; act=1; rez=0;
		back(1); 
		printf("%lld\n",a-rez);
	}
	return 0;
}