#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="pinex.in";
const char OutFile[]="pinex.out";
const int MaxB=(int)(1e12)+1;
const int sqrtMaxB=(int)(1e6)+1;

ifstream fin(InFile);
ofstream fout(OutFile);

long long A,sol;
int M,B;
char pciur[sqrtMaxB];
vector<int> nrp;
vector<int> dp;

inline void ciur()
{
	for(register int i=2;i<sqrtMaxB;++i)
	{
		if(pciur[i]==0)
		{
			nrp.push_back(i);
			for(register int j=i<<1;j<sqrtMaxB;j+=i)
			{
				pciur[j]=1;
			}
		}
	}
}

inline void solve()
{
	sol=0;
	dp.clear();
	for(vector<int>::iterator it=nrp.begin();it!=nrp.end() && (*it)*(*it)<=B;++it)
	{
		int x=*it;
		if(B%x==0)
		{
			dp.push_back(x);
			while(B%x==0)
			{
				B/=x;
			}
		}
	}
	if(B>1)
	{
		dp.push_back(B);
	}

	int maxcfg=1<<(dp.size());
	for(int cfg=1;cfg<maxcfg;++cfg)
	{
		int tcfg=cfg;
		int nrone=0;
		int prod=1;
		for(register int i=0;tcfg;++i,tcfg>>=1)
		{
			if((tcfg&1)==1)
			{
				++nrone;
				prod*=dp[i];
			}
		}
		if((nrone&1)==1)
		{
			sol+=A/prod;
		}
		else
		{
			sol-=A/prod;
		}
	}
	fout<<A-sol<<"\n";
}

int main()
{
	ciur();
	fin>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>A>>B;
		solve();
	}
	fin.close();
	fout.close();
	return 0;
}