#include<fstream>
#include<vector>
#include<cmath>

#define LENGTH 1000005
#define LL long long

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m,sol,v[50],L;
bool prim[LENGTH],use[LENGTH];
LL a,b,p[50];
vector<int> divs;
vector<LL> divs_nr;

void ciur()
{
	for(int i=2;i<LENGTH;i++)
		prim[i]=1;
	for(int i=2;i<LENGTH;i++)
		if(prim[i])
		{
			for(int j=i+i;j<LENGTH;j+=i)
				prim[j]=0;
			divs.push_back(i);
		}
}

void back(int k,int n)
{
	for(int i=v[k-1]+1;i<=n;i++)
	{
		if(use[i])
			continue;
		v[k]=i;
		use[i]=1;
		p[k]=p[k-1]*divs_nr[v[k]];
		if(k%2)
			sol+=a/p[k];
		else
			sol-=a/p[k];
		if(k<n)
			back(k+1,n);
		use[i]=0;
	}
}

int main()
{
	ciur();
	p[0]=1;
	fin>>m;
	while(m--)
	{
		fin>>a>>b;
		divs_nr.clear();
		divs_nr.push_back(0);
		sol=0;
		L=sqrtl(b);
		for(size_t i=0;i<divs.size() && divs[i]<=L && divs[i]<=b;i++)
			if(b%divs[i]==0)
			{
				divs_nr.push_back(divs[i]);
				while(b%divs[i]==0)
					b/=divs[i];
			}
		if(divs_nr.size()==0)
		{
			fout<<a-1<<'\n';
			continue;
		}
		if(b>1)
			divs_nr.push_back(b);
		back(1,divs_nr.size()-1);
		fout<<a-sol<<'\n';
	}
	return 0;
}