/*
	Keep It Simple!
*/


#include<stdio.h>
#include<math.h>
#define MaxD 1000005

long long p[80000],nr,n,NrD,D[80000];
bool viz[MaxD];

void Init()
{
	p[++nr] = 2;
	for(int i=3; i<=MaxD; i+=2)
	{
		if(!viz[i])
		{
			p[++nr]=i;
			
			for(int j=i; j<=MaxD; j+=i)
				viz[j] = 1;
		}
	}
}

void InitNrD(long long x)
{
	NrD = 0;
	for(int i=1; i<=nr && x!=1; i++)
	{
		if( x%p[i] == 0 )
		{
			D[++NrD]=p[i];
			while(x%p[i] == 0)
			{
				x/=p[i];
			}
		}
		if( p[i] > sqrt(x) && x>1)
		{
			D[++NrD] = x;
			x=1;
		}
	}
}

void Solve(long long a,long long b)
{
	long long s = 0;
	
	InitNrD(b);
	
    for( int i = 1; i < (1<<NrD); i++ )
	{
		long long sign = 0 , prod = 1;
		
		for( int j=0; j< NrD; j++)
			if( i & (1<<(j)) )
			{
				prod *= 1LL * D[j+1];
				sign++;
			}
		if( sign%2 == 0)
			sign = -1;
		else
			sign = 1;
		
		s += 1LL * sign * a/prod;
	}
	
	printf("%lld\n",a-s);
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	Init();
	
	scanf("%lld",&n);
	
    long long x,y;
	
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		Solve(x,y);
	}
}