// Include
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

// Definitii
#define pb push_back
#define ll long long

// Constante
const int PRIMESZ = (ll)1e6+1LL;

// Functii
void erath();

// Variabile
ifstream in("pinex.in");
ofstream out("pinex.out");

int tests;
ll num, primeWith;

bitset<PRIMESZ+5> primeBool;
vector<ll> primes, divisor;

// Main
int main()
{
	erath();
	
	vector<ll>::iterator it, end;
	
	in >> tests;
	while(tests--)
	{
		in >> num >> primeWith;
		divisor.clear();
		
		for(it=primes.begin() ; *it <=primeWith ; ++it)
		{
			if(!(primeWith % *it))
			{
				divisor.pb(*it);
				do
					primeWith /= *it;
				while(!(primeWith % *it));
			}
		}
		if(primeWith != 1)
			divisor.pb(primeWith);
		
		ll answer = 0;
		
		int limit = 1<<divisor.size();
		for(int i=1 ; i<limit ; ++i)
		{
			ll bits = 0, prod=1LL;
			for(int j=0 ; (1<<j)<=i ; ++j)
			{
				if((1<<j) & i)
				{
					++bits;
					prod *= divisor[j];
				}
			}
			if(bits&1)
				answer += num/prod;
			else
				answer -= num/prod;
		}
		out << num - answer << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

void erath()
{
	primeBool.flip();
	primes.pb(2);
	for(ll i=3 ; i<PRIMESZ ; i+=2)
	{
		if(primeBool[i])
		{
			if(i*i > 0) // Daca n-a iesit din ll
				for(ll j=i*i ; j<PRIMESZ ; j+=i)
					primeBool[j] = false;
			primes.pb(i);
		}
	}
	primes.pb((1<<30)-1); // Infinit, sa se opreasca din while
}