#include <cstdio>
#define pmax 1000000
#define nmax 80010
#define ll long long

bool u[pmax+5];
int v[nmax], m, l, h, f[33];
ll a, b;

void factorizare (int n)
{
	int i=1, c;
	while (n > 1)
	{
		if (v[i] * v[i] > n) break;
		c=0;
		while (! (n%v[i]))
		{
			c++;
			n /= v[i];
		}
		if (c) f[++l] = v[i];
		i++;
	}
	if (n>1) f[++l] = n;
}

int main()
{
	freopen ("pinex.in", "r",stdin);
	freopen ("pinex.out", "w", stdout);
	int i, d, c, j;
	ll p;
	scanf ("%d", &m);
	
	for (d=2; d <= pmax; d++)
		if (!u[d])
		{
			v[++h] = d;
			for (i=d; i <= pmax; i+=d) u[i]=1;
		}
	
	while (m--)
	{
		scanf ("%lld %lld", &a, &b);
		l = 0;
		factorizare (b);
		ll sol = a;
		for (i=1; i < (1<<l); i++)
		{
			p = 1;
			c = 0;
			for (j=0; j<l; j++)
				if ((1<<j) & i)
				{
					c++;
					p *= f[j+1];
				}
			if (c&1) p = -p;
			sol += a/p;
		}
		printf ("%lld\n", sol);
	}
}