#include<stdio.h>
char viz[101000];
long long A,B,prim[25000],nrp[16],npr,sol;
void ciur(){
	int i,j,n=100900;
	for(i=3;i<=n;i+=2){
		for(j=i+(i<<1);j<=n;j+=i<<1)
			viz[j]=1;
	}
	prim[++prim[0]]=2;
	for(i=3;i<=n;i+=2){
		if(!viz[i])
			prim[++prim[0]]=i;
	}
}
void calcp(){
	long long b=B;
	for(int i=1;prim[i]*prim[i]<=b;++i){
		if(b%prim[i]==0){
			nrp[++npr]=prim[i];
			while(b%prim[i]==0)
				b/=prim[i];
		}
	}
	if(b>1)
		nrp[++npr]=b;
}
void solve(){
	sol=0;
	npr=-1;
	calcp();
	int i,j,p;
	long long c;
	for(i=1;i<(1<<(npr+1));++i){
		c=1;
		for(p=0,j=0;(1<<j)<=i;++j){
			if(i&(1<<j)){
				++p;
				c*=nrp[j];
			}
		}
		if(p&1)
			sol+=A/c;
		else
			sol-=A/c;
	}
	printf("%lld\n",A-sol);
}
int main(){
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	int t;
	ciur();
	scanf("%d",&t);
	for(;t;--t){
		scanf("%lld%lld",&A,&B);
		solve();
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}