#include<stdio.h>
#include<math.h>
FILE*f=fopen("pinex.in","r");
FILE*g=fopen("pinex.out","w");
int m,o,z,k,v[100000],vv[20];
long long a,b,s[20],sol1;
char w[1000001];
void tipar(int x){
	long long sol=1;
	int nr=0;
	for(int dd=1;dd<=z;++dd){
		if(s[dd]==1){
			sol*=vv[dd];
			nr++;
		}
	}
	if (nr)
		if(nr%2)
			sol1+=a/sol;
		else
			sol1-=a/sol;
}
void back(int x){
	if(x>z)
		tipar(z);
	else
		for(int ff=0;ff<=1;++ff){
			s[x]=ff;
			back(x+1);
		}
}
int main(){
	fscanf(f,"%d",&m);
	for(int i=2;i<=1000000;++i)
		if(!w[i]){
			for(int j=2*i;j<=1000000;j+=i)
				w[j]=1;
			v[++k]=i;
		}
	
	for(int o=1;o<=m;++o){
		sol1=0;
		fscanf(f,"%lld%lld",&a,&b);
		z=0;
		long long x=b;
		long long y=sqrt(x);
		for(int j=1;j<=k&&x>1&&v[j]<=y;++j)
			if(x%v[j]==0){
				while(x%v[j]==0)
					x/=v[j];
				vv[++z]=v[j];
			}
		if(x>1)
			vv[++z]=x;
		back(1);
		fprintf(g,"%lld\n",a-sol1);
	}
	fclose(g);
	fclose(f);
	return 0;
}