#include<fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int i,j,k,t,s,n,P[100000],v[1000001],nd;
long long x,y,u,pd,d[15];
int main()
{
	for(i=2;i<=1000000;i++)
	{
		if(v[i]==0)
		{
			P[++k]=i;
			for(j=i+i;j<=1000000;j=j+i)
				v[j]=1;
		}
	}
	f>>n;
	for(i=1;i<=n;i++)
	{
		f>>x>>y;u=y;s=0;t=0;
		for(j=1;u!=1&&P[j]*P[j]<=y;j++)
		{
			if(u%P[j]==0){
				d[++t]=P[j];
				while(u%P[j]==0)
					u=u/P[j];
			}
		}
		if(u!=1) {
			d[++t] = u;
		}
		
		for (j=0;j<=t;j++)
			v[j] = 0;
		while (v[0]!=1)
		{
			j=t;
			while(v[j]==1)
			{
				v[j]=0;
				j--;
			}
			v[j]=1;
			
			if (v[0] == 1)
				break;
			
			pd = 1;
			nd = 0;
			for (j=1;j<=t;j++)
			{
				if(v[j]==1)
				{
					nd++;
					pd=pd*d[j];
				}
			}
			if(nd%2==0)
				s=s-x/pd;
			else
				s=s+x/pd;
			
		}
		
		g<<x-s<<"\n";
		
	}
			
	return 0;
	
}