#include<fstream.h>
ifstream f("pinex.in"); ofstream g("pinex.out");
char ciur[1000001]; //ciur[i] == 0 daca i este prim
long long a,b,sum,s,pr,p[100001],d[30];
int T,i,j,n,nr=0,m,k,x[30];
void prelsol()
{long long pr=1;
 for(int i=1; i<=n; i++) pr=pr*d[x[i]];
 s+=a/pr;
}
void back()
{s=0; k=1; x[k]=0;
 do {while(x[k]<m)
		{x[k]++;
		 if(k==n) prelsol(); 
		  else {k++; x[k]=x[k-1];};
		}
	 k--;	
	}
 while(k); 
 if(n%2) sum+=s; else sum-=s;
} 
int main()
{for(i=2; i<=500000; i++)
  if(!ciur[i])
   {p[++nr]=i;
	for(j=i+i; j<=1000000; j+=i) ciur[j]=1;
   };
 f>>T;
 while(T)  
   {f>>a>>b;
	m=0; i=1;
    while(b>1 && p[i]*p[i]<=b)
	  {if(b%p[i]==0)
		  {d[++m]=p[i];
		   while(b%p[i]==0) b/=p[i];
		  };
		i++;
	  }
	if(b>1) d[++m]=b;
	sum=0; 
	for(n=1; n<=m; n++)
		back();
	g<<a-sum<<'\n';  
	T--;
   }
 g.close(); return 0;
}
/*
#include<stdio.h>
#include<math.h>
#define Nmax 80000
using namespace std;

long long S,Sum,Pr,i,m,A,B,T,t,prim[Nmax],dprim[Nmax],D,x[Nmax],P,ciur[1000001];


void back(int k,int n)
{
	int i;
	
	for(i=x[k-1]+1;i<=D;i++)
	{
		x[k]=i;
		Pr*=dprim[x[k]];
		
		if(k==n)
		{
			S+=A/Pr;
			Pr/=dprim[x[k]];
		}
		else
		{
			back(k+1,n);
			Pr/=dprim[x[k]];
		}
	}
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%d",&T);
	precalc();
	for(t=1;t<=T;t++)
	{
		scanf("%lld %lld",&A,&B);
		
		D=0; m=smrt(B);
		
		for(i=1; i<=m && B>1 ; i++)
		{
			if(B%prim[i]==0) 
			{
				dprim[++D]=prim[i];
				while(B%prim[i]==0) B/=prim[i];
			}
		}
		if(B>1) dprim[++D]=B;
		Sum=0;
		for(i=1;i<=D;i++)
		{
			S=0; Pr=1;
			back(1,i);
			if(i&1) Sum+=S;
			else Sum-=S;
		}
		
		printf("%lld\n",A-Sum);
	}
	return 0;
}
*/