#include<fstream>
#define NM 1000100
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int i,v[NM],p[NM],use,S[NM],k,u,n,j,t,N;
long long cur,a,b,sol;
void calc(int x)
{
	if(x>u)
		return;
	int val;
	for(int i=use+1;i<=u;++i)
	{
		if(x%2)
		{
			cur*=S[i];
			sol+=a/cur;
			val=use;
			use=i;
			calc(x+1);
			cur/=S[i];
			use=val;
		}
		else
		{
			cur*=S[i];
			sol-=a/cur;
			val=use;
			use=i;
			calc(x+1);
			cur/=S[i];
			use=val;
		}
	}
}
int main ()
{
	N=1000000;
	for(i=2;i<=N;++i)
		if(!v[i])
			for(j=2*i;j<=N;j+=i)
				v[j]=1;
	for(i=2;i<=N;++i)
		if(!v[i])
			p[++t]=i;
	f>>n;
	for(i=1;i<=n;++i)
	{
		f>>a>>b;
		u=0;
		for(k=1;p[k]*p[k]<=b;++k)
		{
			if(b%p[k]==0)
			{
				S[++u]=p[k];
				while(b%p[k]==0)
					b/=p[k];
			}
		}
		if(b!=1)
			S[++u]=b;
		sol=0;
		cur=1;
		calc(1);
		g<<a-sol<<"\n";
	}
	return 0;
}