#include<stdio.h>
#include<math.h>
#define Nmax 80000
using namespace std;

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


void precalc()
{
	int n,i,j;
	n=1000000;
	for(i=2;i<=n;i++)
	{
		if(ciur[i]==0)
		{
			prim[++P]=i;
			for(j=i+i;j<=n;j+=i)
				ciur[j]=1;
		}
	}
}

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("%d %d",&A,&B);
		
		D=0; m=sqrt(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("%d\n",A-Sum);
	}
	return 0;
}