#include <fstream>
#include <cmath>

using namespace std;

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

const int MAX_PRIM = 1000000;

int N, prime[MAX_PRIM], nrprimes, diviz[MAX_PRIM];
bool prim[MAX_PRIM + 5];

void ciur() {
	for (int i = 2; i <= MAX_PRIM; i++)
		prim[i] = 1;
	
	for (int i = 2; 1LL * i * i <= MAX_PRIM; i++) {
		if (prim[i]) {
			for (int j = i * i; j <= MAX_PRIM; j += i)
				prim[j] = 0;
		}
	}
	
	for (int i = 2; i <= MAX_PRIM; i++)
		if (prim[i])
			prime[++nrprimes] = i;
}

void solve(long long A, long long B) {
	int ind = 0;	// indicele pentru numerele prime
	int nrdiv = 0;
	long long sol = A;
	
	// aflu divizorii primi a lui B in O(sqrt(B))
	while (B > 1) {
		ind++;
		if (B % prime[ind] == 0) {
			diviz[++nrdiv] = prime[ind];
			while (B % prime[ind] == 0)
				B /= prime[ind];
		}
		
		if (prime[ind] > sqrt((double)B) && B > 1) {
			diviz[++nrdiv] = B;
			B = 1;
		}
	}
	
	// |A1 U A2 U A3 U ... U An| = |A1| + |A2| + .. + |An| - comb(n, 2) + comb(n, 3) - ...
	// numai intersectii		|A1 and A2| = |A / (diviz[1] * diviz[2])|
	
	for (int i = 1; i < (1 << nrdiv); i++) {
        long long nr = 0, prod = 1;
        for (int j = 0; j < nrdiv; j++)
            if ((1 << j) & i) {
                prod = 1LL * prod * diviz[j + 1];
                nr++;
            }
		
		if (nr % 2 == 1)
			nr = - 1;
		else
			nr = 1;
		sol = sol + 1LL * nr * A / prod;
    }
	
	g << sol << '\n';
}

int main() {
	ciur();
	
	f >> N;
	for (int i = 1; i <= N; i++) {
		long long A, B;
		f >> A >> B;
		solve(A, B);
	}
	
	f.close();
	g.close();
	
	return 0;
}