#include <fstream>
#include <iostream>
#include <cmath>
#define MAXP 120000
#define MAXV 1001000
#define MAXF 100

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long prime[MAXP];
bool v[MAXV];
long long factors[MAXF];

int sieve(int n) {
	long long i,j;
	int k = 0;

	prime[k++] = 2;
	for(i = 3; i < n; i += 2)
		if(!v[i]) {
			prime[k++] = i;
			for(j = i*i; j <= n; j += i)
				v[j] = true;
		}
	return k;
}

int factorize(long long n, long long max) {
	long long k = 0, sqr = ceil(sqrt(n)), d = 0;

	while(n > 1 && prime[k] <= sqr && k < max) {
		if(n%prime[k] == 0) {
			n /= (long long)prime[k];
			if(factors[d-1] != prime[k])
				factors[d++] = prime[k];
		}
		else 
			k++;
	}
	if(n > 1) {
		factors[d] = n;
		return d+1;
	} else
		return d;
}

int main() {
	long long m,i,j,nrf,nr,k,pn;
	long long prod,a,b,s;

	pn = sieve(MAXP);
	
	f>>m;
	for(k = 0; k < m; k++) {
		f>>a>>b;
		nrf = factorize(b,pn);

		s = 0;
		for(i = 1; i < (1<<nrf); i++) {
			prod = 1;
			nr = 0;
			for(j = 0; j < nrf; j++)
				if((1<<j) & i) {
					prod = prod * factors[j];
					nr++;
				}
			s += a/prod * (long long)((nr %2) ? -1 : 1);
		}
		g<<s+a<<"\n";
	}

	return 0;
}