#include <bits/stdc++.h>
using namespace std;
#define pmax 1000000
#define nmax 80010
bool ciur[pmax+5];
long long  nr_div;
long long prime[nmax],fact[33];
void factorizare (long long n){
	long long i=1;
	while(prime[i]*prime[i]<=n){
        long long e=0;
		while(n%prime[i]==0){
			++e;
			n/=prime[i];
		}
		if(e>0)
            fact[++nr_div]=prime[i];
		++i;
	}
	if(n>1)
        fact[++nr_div]=n;
}
int main(){
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
    long long nr_prime=0;
	for(long long d=2;d<=pmax;++d)
		if(!ciur[d]){
			prime[++nr_prime]=d;
			for(long long i=d*d;i<=pmax;i+=d)
                ciur[i]=1;
		}
    long long m;
    scanf("%lld",&m);
	while(m--){
        long long a,b;
		scanf("%lld %lld",&a,&b);
		nr_div=0;
		factorizare(b);
		long long sol=a;
		for(long long i=1;i<(1<<nr_div);++i){
			long long p=1,c=0;
			for(long long j=0;j<nr_div;++j)
				if((1<<j)&i){
					c++;
					p*=fact[j+1];
				}
			if(c%2==1)
                p=-p;
			sol+=a/p;
		}
		printf("%lld\n",sol);
	}
}