#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

#define ll long long


using namespace std;

ifstream fcin("pinex.in");
ofstream fcout("pinex.out");


const int LIM = 1e6 + 10;
vector< ll > primes;
int sievv[LIM];

void sieve( )
{
	int gy = sqrt( LIM - 10 );
	for( int i = 2; i <= gy; ++i )
		if( !sievv[i] )
			for( int j = i * i; j < LIM; j += i )
				sievv[j] = 1;
	
	for( int i = 2; i < LIM; ++i )
		if( !sievv[i] )
			primes.push_back( i );
}


ll m;
ll N;
ll maxD;
ll A, B;
ll sum;
ll summult = 1;

ll nrn;
ll numbers[LIM];

ll J[LIM];

void f( int d )
{
	if( d == maxD )
	{
		// J is legit:
		// can add to sum
		ll mult = 1;
		for( int i = 1; i <= maxD; ++i )
		{
			mult *= numbers[J[i] - 1];
		}
		
		sum += ( A / mult ) * summult;
		return;
	}

	
	for( int i = J[d] + 1; i <= N; ++i )
	{
		J[d + 1] = i;
		f( d + 1 );
		// J[d + 1] = 0;
	}
}


void solve(  )
{
	// prime divisors of B
	//vector< int > numbers;
	ll gy = sqrt( B );
	nrn = 0;
	for( int i = 0; i < primes.size() && primes[i] <= B; ++i )
	{
		if( B % primes[i] == 0 )
			numbers[nrn++] = primes[i];
	}
	N = nrn;
	// |a[i]| = A/numbers[i]
	// |a[i]^a[j]| = A/(numbers[i]*numbers[j])
	sum = 0;
	summult = 1;
	for( int i = 1; i <= N; ++i )
	{	
		maxD = i;
		f( 0 );
		summult *= -1;

		
	}
	
	fcout << A - sum << "\n";

}

int main()
{
	sieve();
	fcin >> m;
	while( m-- )
	{
		fcin >> A >> B;
		solve();
	}

}