#include <cstdio>
#include <cmath>

typedef long long ll;

using namespace std;

ll T, A, B;

ll primes[40];
ll result;

int N;

void read() {
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
}

void inline divide(int k) {
	while(!(B % k)) {
		B = B / k;
	}
}

void getPrimes() {
	N = 0;
	for( int i = 2; i <= sqrt(B); i++ )
		if( B % i == 0 ){
			primes[N] = i;
			N++;
			divide(i);
		}

	if ( B != 1 ) {
		primes[N] = B;
		N++;
	}
}

ll inline getFactor(ll count) {
	ll p = 1;
	int k = 0;
	while( k < N ){
		if ( count & 1 )
			p *= -1;
		else
			p *= primes[k];
		k++;
		count >>= 1;
	}
	return A / p;
}

void compute() {
	result = 0;
	ll count = 1 << N;
	while( count ) {
		ll r = getFactor(count);
		result += r;
		count--;
	}

	if( result > 0 )
		printf("%lld\n", result);
	else
		printf("%lld\n", -result);
}

int main() {
	read();
	scanf("%i", &T);
	while( T ) {
		scanf("%lld %lld", &A, &B);
		getPrimes();
		compute();
		T--;
	}
	return 0;
}