// 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<int> primes, divisor;

// Main
int main()
{
	erath();
	
	vector<int>::iterator it, end;
	
	in >> tests;
	while(tests--)
	{
		in >> num >> primeWith;
		divisor.clear();
		
		while(primeWith != 1)
		{
			for(it=primes.begin(),end=primes.end() ; it!=end && *it <=primeWith ; ++it)
			{
				if(!(primeWith % *it))
				{
					divisor.pb(*it);
					do
						primeWith /= *it;
					while(!(primeWith % *it));
				}
			}
		}
		
		ll answer = 0;
		
		ll limit = 1LL<<divisor.size();
		for(ll i=1LL ; i<limit ; ++i)
		{
			ll bits = 0, prod=1LL;
			for(ll j=0 ; (1LL<<j)<=i ; ++j)
			{
				if((1LL<<j) & i)
				{
					++bits;
					prod *= divisor[j];
				}
			}
			if(bits&1LL)
				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(int i=3 ; i<PRIMESZ ; i+=2)
	{
		if(primeBool[i])
		{
			if(i*i > 0) // Daca n-a iesit din int
				for(int j=i*i ; j<PRIMESZ ; j+=i)
					primeBool[j] = false;
			primes.pb(i);
		}
	}
}