#include <stdio.h>
#include <math.h>
#define max 1000005
#define LL long long

bool p[max];
int d[100005],fp[35];
LL A,B;
int t,z;

void ciur(){
	int i,j;
	for(i=2;i<max;++i){
		if(!p[i]){
			d[++z]=i;
			for(j=2*i;j<max;j+=i)
				p[j]=1;
		}
	}
}

void work(){
	LL prod,nr,rez;
	int i,j;
	fp[0]=0;
	
	for(i=1;i<=z && B>1 ;++i){
		if(B % d[i]==0){
			fp[++fp[0]]=d[i];
			while(B % d[i]==0) B/=d[i];
		}
		if(d[i]>sqrt(B) && B>1){
			fp[++fp[0]]=B;
			B=1;
		}
	}
	
	rez=0;
	for(i=1; i<(1<<fp[0]); ++i){
		prod=1; nr=0;
		for(j=0; j<fp[0] ; ++j)
			if(i & (1<<j) ){
				nr++;
				prod=(LL)prod * fp[j+1];
			}
		if(nr&1) rez= rez + A/prod;
		else rez= rez - A/prod;
	}
	printf("%lld\n",A-rez);
}

int main(){
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	ciur();
	
	for(scanf("%d",&t); t; --t){
		scanf("%lld %lld",&A,&B);
		work();
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}