#include <fstream>
#include <algorithm>
#include <vector>
#define pmax 1000000
#define ll long long
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
vector<ll> prim;
bool c[1000001];
ll t,a,b;
void ciur()
{
	for(ll i=2;i<=pmax;i++)
	{
		if(c[i]) continue;
		prim.push_back(i);
		for(ll j=i*i;j<=pmax;j+=i)
			c[j]=1;
	}
}
bool use[1000001];
vector<int> fact;
ll bkt(int pos,int lg)
{
	if(lg==0)
	{
		ll p=1;
		for(int i=0;i<fact.size();i++)
		{
			if(use[i])
				p*=fact[i];
		}
		return a/p;
	}
	ll x=0;
	for(int i=pos;i<fact.size();i++)
	{
		if(!use[i])
		{
			use[i]=1;
			x+=bkt(i+1,lg-1);
			use[i]=0;
		}
	}
	return x;
}

int main()
{
	ios_base::sync_with_stdio(false);
	ciur();
	cin>>t;
	while(t--)
	{
		fact.clear();
		cin>>a>>b;
		for(int i:prim)
		{
			if(b%i==0)
				fact.push_back(i);
			if(i>b)
				break;
		}
		ll ans=a;
		for(int i=1;i<=fact.size();i++)
		{
			if(i%2)
				ans-=bkt(0,i);
			else
				ans+=bkt(0,i);
		}
		cout<<ans<<'\n';
	}
}