#include <cstdio>

using namespace std;

#define MAXN 1000003


bool er[MAXN];
int primes[MAXN];
int primesno;
int divs[40];


void erathostenes() {
	primes[1] = 2;
	primesno = 1;
	for(int i=3; i<MAXN; i+= 2)
		if (! er[i]) {
			primes[++primesno] = i;
			for(int j = i + i; j<MAXN; j += i)
				er[j] = true;
		}
}



long long solve(long long a, long long b) {
	int divsno = 0, bitno = 0;
	long long prod = 1, sol = a;

	for(int i=1; i <= primesno && primes[i] * primes[i] <= b && b > 1; ++i) {
		if (b % primes[i] == 0)
			divs[++divsno] = primes[i];

		while(b % primes[i] == 0)
			b /= primes[i];
	}

	if (b > 1)
        divs[++divsno] = b;

	for(int i=1; i < (1<<divsno); ++i) {
		bitno = 0;
		prod = 1;
		for(int j=1; j<=divsno; ++j)
			if ( (1<< (j-1)) & i) {
				prod *= divs[j];
				++bitno;
			}

		if (bitno % 2)
			prod = -prod;

		sol += a / prod;
	}

	return sol;
}



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

	int n;
	long long a, b;
    scanf("%d", &n);

    erathostenes();

	for(int i=0; i<n; ++i) {
		scanf("%lld%lld", &a, &b);
		printf("%lld\n", solve(a, b));
	}

	return 0;
}