#include <cstdio>
#include <cmath>

typedef long long ll;

using namespace std;

ll A, B;

char q[1000000];
int p[78500];
ll primes[40];
ll result;

int T, N, P = 0;

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

void computePrime() {
	for( int i = 2; i < 1000000; i++ )
		if( !q[i] ){
			p[P] = i;
			P++;
			for( int j = 2 * i; j < 1000000; j+=i )
				q[j] = 1;
		}
}

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

void getPrimes() {
	N = 0;
	int i = 0;
	while( p[i] < sqrt(B) && i < P) {
		if( !(B % p[i]) ) {
			primes[N] = p[i];
			N++;
			divide(p[i]);
		}
		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);
	computePrime();
	while( T ) {
		scanf("%lld %lld", &A, &B);
		getPrimes();
		compute();
		T--;
	}
	return 0;
}