/* ugly */
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;

#define P_LIM 1000000
#define div_max 80010

vector< int > P;

long long D[div_max];
bool viz[P_LIM];

void prim()
{
	int i,j;

	viz[1]=1;

	P.push_back( 2 );
	for(i=2; i<=P_LIM; i+=2)
		viz[i]=1;

	for(i=3; i<=P_LIM; i+=2)
	{
		if( !viz[i] )
		{
			P.push_back(i);
			for(j=i+i; j<=P_LIM; j+=i)
				viz[j]=1;
		}
	}

	return;
}

void find_div( long long nr )
{
	D[0]=0;

	if( nr<P_LIM && !viz[nr] )
	{
		D[++D[0]]=nr;
		return;
	}

	unsigned int i,sz=P.size();
	for(i=0; i<sz && nr>1; ++i)
	{
		int p=P[i];
	
		if( nr%p == 0 )
		{
			D[ ++D[0] ]=p;
			while( nr%p==0 )
				nr/=p;
		}
	}

	if( nr!=1 )
	{
		long long i=0;
		for(i=P[sz-1]+2; i*i<=nr; i+=2)
		{
			if( nr%i==0 )
			{
				D[ ++D[0] ]=i;
				while( nr%i==0 )
					nr/=i;
			}
		}
	}

	if( nr!=1 ) // it's probably prime
		D[++D[0]]=nr;
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);

	prim();

	int M;
	scanf("%d",&M);

	long long A,B;
	while( M-- )
	{
		scanf("%lld%lld\n",&A,&B);

		find_div( B );
		
		long long i,sz=D[0],j;
		long long CFG= (1<<(sz)),ANS=A;
		for(i=1; i<CFG; ++i)
		{
			long long cfg_type=0,count=1;
			for(j=0; j<sz; ++j)
			{
				if( i&(1<<j) )
				{
					++cfg_type;
					count*=D[j+1];
				}
			}

			if( cfg_type%2==0 )
				ANS+=A/count;
			else
				ANS-=A/count;
		}
	
		printf("%lld\n",ANS);
	}

	return 0;
}