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

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

// Constante
const int sz = (int)1e6+2;

// Functii
void eratosthenes();

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

int questions;
ll num, primeWith;

vector<int> primeNumbers, divisors;

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

void eratosthenes()
{
	bool noPrime[sz];
	memset(noPrime, false, sizeof(noPrime));
	
	primeNumbers.pb(2);
	
	for(int i=3 ; i<sz ; i+=2)
	{
		if(!noPrime[i])
		{
			for(int j=i+i ; j<sz ; j+=i)
				noPrime[j] = true;
			primeNumbers.pb(i);
		}
	}
}