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

using namespace std;

typedef long long ll;

ll ans =0;
vector<int> pp;
void qq(ll x, ll y)
{
	ans = 0;
	pp.clear();
	for (ll i=2; i*i<=y; i++)
		if (y%i==0) {pp.push_back(i);while(y%i==0) y/=i;}
	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;
	while (m--)
	{
		ll a,b;
		cin>>a>>b;
		qq(a,b);
		cout<<ans<<'\n';
	}
	return 0;
}