#include <cstdio>
#include <vector>
#include <cmath>

const unsigned PR_SUB_MIL=78498; //sunt 78498 prime sub 10^6
unsigned primes[PR_SUB_MIL];

void preprocess(){
	unsigned c=1; primes[0]=2;
	std::vector<bool> pr(499999,true);
	for(unsigned i=0;i<499999;++i) if(pr[i]){
			unsigned a=2*i+3;
			primes[c++]=a;
			for(unsigned j=3;a*j<1000000;j+=2)
				pr[(a*j-3)>>1]=false;
		}
}

inline long long get(long long a, long long b){
	long long fact[7]; //produsul a 8 prime ar depasi 10^6
	unsigned nrfact=0;

	for(unsigned i=0;primes[i]<=std::sqrt(b)&&b>1;++i) if(b%primes[i]==0){
		fact[nrfact++]=primes[i];
		while(b%primes[i]==0) b/=primes[i];
	}
	if(b>1) fact[nrfact++]=b;

	long long sol=a;

	for(unsigned i=1;i<(1u<<nrfact);++i){
		long long nr=0; long long prod=1;
		for(unsigned j=0;j<nrfact;++j)
			if((1<<j)&i){
				++nr;
				prod*=fact[j];
			}

		if(nr&1) nr=-1;
		else nr=1;
		sol += nr * a / prod;
	}

	return sol;
}

int main(){
	std::freopen("pinex.in","r",stdin);
	std::freopen("pinex.out","w",stdout);

	preprocess();

	unsigned m; scanf("%u",&m);
	while(m--){
		long long a,b;
		scanf("%lld %lld",&a,&b);
		printf("%llu\n",get(a,b));
	}
}