#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

typedef long long ll;

vector<int> primes;
void sieve()
{
	bool ss[1000002];
	fill(ss,ss+1000002,1);
	ss[1]=0;
	ss[0]=0;
	for (int i=2; i<=1000000; i++)
		if (ss[i])
		{
			for (int j=2; j*i<=1000000; j++)
				ss[j*i]=0;
			primes.push_back(i);
		}
}

ll ans =0;
vector<int> pp;
void qq(ll x, ll y)
{
	ans = 0;
	pp.clear();
	for (ll i:primes)
	{
		if (y%i==0) {pp.push_back(i);while(y%i==0) y/=i;}
		if (i*i>y) break;
	}
	if (y>1) pp.push_back(y);

	int sz = pp.size();
	for (int i=1; i< 1<<sz; i++)
	{
		ll c;
		c = 1;
		int k=0;
		for (int j=0; 1<<j <=i && c<=x; j++)
			if (i&(1<<j))
			{
				k++;
				c*=pp[j];
			}
		c = x/c;
		if (k%2) ans+=c;
		else ans-=c;
	}
	ans = x-ans;
}

int main()
{
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	int m;
	cin>>m;
	sieve();
	while (m--)
	{
		ll a,b;
		cin>>a>>b;
		qq(a,b);
		cout<<ans<<'\n';
	}
	return 0;
}