#include<fstream>
#include<bitset>
#include<vector>
using namespace std;
#define mn 1000000
ifstream f("pinex.in");
ofstream g("pinex.out");
long long  i,j,A,B,M;
bitset<mn+1>v;
vector<int>primes;
long long a[mn/2];
void ciur()
{	for(i=2;i<=mn;i++)
		if(v[i]==0)
		{	for(j=i<<1;j<=mn;j+=i)
				v[j]=1;
			primes.push_back(i);
		}
}
void solve()
{	long long aux=B,k=1,s=0,p=1,pf;
	for(i=0;primes[i]<<1<=B && aux!=1;i++)
	{	if(aux%primes[i]==0)
		{	while(aux%primes[i]==0)
				aux/=primes[i];
			a[k]=primes[i];
			k++;
			s+=A/primes[i];
			p*=primes[i];
		}
	}
	if(aux!=1)
		a[k]=aux , s+=A/aux , p*=aux , k++;
	if(k>3)
	{	pf=s+A/p;
		for(i=1;i<k;i++)
			for(j=i+1;j<k;j++)
				pf-=A/(a[i]*a[j]);
		g<<A-pf<<'\n';
	}
	else
		if(k>2)
			g<<A-(s-A/p)<<'\n';
		else
			g<<A-s<<'\n';
}
int main()
{	ciur();
	f>>M;
	for(int i=1;i<=M;i++)
	{	f>>A>>B;
		solve();
	}
	f.close();
	g.close();
	return 0;
}