#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int primes[10000];

void initPrimes()
{
	const int MAX = 1000 * 1000;
	primes[0] = 0;
	int a[MAX];
	memset(a, 0, sizeof(a));
	for(int i=2;i<MAX;++i)
		if (a[i] == 0)
		{
			primes[++ primes[0]] = i;
			for(int j=i+i;j<MAX;j+=i)
				a[i]=1;
		}
}

int main()
{
	initPrimes();
	int m;
	long long a, b, n, c;
	int sig;

	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	long long divs[100];
	scanf("%d", &m);

	while (m --)
	{
		scanf("%lld %lld", &a, &b);
		
		divs[0] = 0;
		for(unsigned int i=1;i<=primes[0] && b!=1; ++ i)
			if (b % primes[i] == 0)
			{
				divs[++ divs[0]] = primes[i];
				while (b % primes[i] == 0) b /= primes[i];
			}
		if(b != 1) divs[++ divs[0]] = b;
		
		n = a;
		int upperLimit = 1 << divs[0];
		for(int i=1;i<upperLimit;++i)
		{
			c = 1;
			sig = 1;
			for(int j=1, k=1; j<=i; j<<=1, ++ k)
				if(i&j)
					c *= divs[k], sig = -sig;
			n += a / c * sig;
		}
		printf("%lld\n", n);
	}

	return 0;
}