#include <cstdio>
#include <cmath>

const int SIEVE_SIZE(1000000);
const int PRIMES_SIZE(100000);
const int DIVISORS_SIZE(15);
const int MAX_VALUE(1 << 30);

int m;
long long a, b, result, factors;
bool sieve [SIEVE_SIZE];
int primes [PRIMES_SIZE];
int divisor [DIVISORS_SIZE];

inline void Eratostene (void)
{
	*primes = 2;
	int divisor, multiple, jump;
	int *add(primes + 1);
	for (divisor = 3 ; divisor < SIEVE_SIZE ; divisor += 2)
		if (!sieve[divisor])
		{
			*add = divisor;
			++add;
			for (jump = divisor << 1, multiple = divisor + jump ; multiple < SIEVE_SIZE ; multiple += jump)
				sieve[multiple] = true;
		}
	*add = MAX_VALUE;
}

inline void decompose (void)
{
	factors = 0;
	int factor, *iterator(primes), root(std::sqrt(b));
	while (*iterator <= root && b > 1)
	{
		if (!(b % *iterator))
		{
			divisor[factors] = factor = *iterator;
			while (!(b % factor))
				b /= factor;
			++factors;
		}
		++iterator;
	}
	if (b > 1)
	{
		divisor[factors] = b;
		++factors;
	}
}

inline void inclusion_exclusion (void)
{
	result = 0;
	const int SUBSETS(1 << factors);
	int bit, elements;
	long long cardinal;
	for (int subset(1) ; subset < SUBSETS ; ++subset)
	{
		for (cardinal = 1, elements = bit = 0 ; bit < factors ; ++bit)
			if (subset & (1 << bit))
			{
				cardinal *= divisor[bit];
				++elements;
			}
		if (elements % 2)
			result += a / cardinal;
		else
			result -= a / cardinal;
	}
	result = a - result;
}

int main (void)
{
	Eratostene();
	std::freopen("pinex.in","r",stdin);
	std::freopen("pinex.out","w",stdout);
	std::scanf("%d",&m);
	while (m)
	{
		std::scanf("%lld %lld",&a,&b);
		decompose();
		inclusion_exclusion();
		std::printf("%lld\n",result);
		--m;
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}