#include <cstdio>
#include <bitset>
#include <cstring>
#define MAX_L 1000001
#define MAX_D 1000010
#define ll long long

using namespace std;

bool dive [MAX_D] ; // a prime number is a dive. Or not ? :)
int divt [MAX_D], fact [MAX_D], T, i, j, nrt; 
void eratosthene ()
{
	divt [++nrt] = 2;
	memset (dive, true, sizeof (dive) );
	for (i = 2; i <= MAX_L; i += 2) dive [i] = false;
	for (i = 3; i <= MAX_L; i += 2)
		if (dive [i] == true)
		{   
			divt [++nrt] = i;
			for (j = i + i; j <= MAX_L; j += i)
				dive [j] = false;
		}
}
ll query (ll A, ll B)
{   
	int k = 0, nr;
	ll sol = 0, pr;
	for (i = 1; i <= nrt && divt[i] * divt[i] <= B; i++)
	{   
		if (B % divt [i] == 0) 
		{
			fact [++k] = divt[i];
		    while (B % divt[i] == 0) B /= divt[i];
		}
	}
	if (B != 1) fact [++k] = B;
	for (i = 1; i < (1 << k); i++)
	{   
		pr = 1, nr = 0;
		for (j = 0; j < i; j++)
		    if ( i & (1 << j) )
			{
				pr = 1LL * pr * fact [j+1];
				++nr;
			}
		if (nr % 2) nr = 1;
		else nr = -1;
		sol = sol + 1LL * nr * A / pr;
	}
	return sol;
}

int main ()
{
	freopen ("pinex.in", "r", stdin);
	freopen ("pinex.out", "w", stdout);
	ll a, b;
	eratosthene ();
	scanf ("%d\n", &T);
	while (T--)
	{
		scanf ("%lld%lld\n", &a, &b);
		printf ("%lld\n", a - query (a, b));
	}
	return 0;
}