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

vector<int> primes;

void initPrimes()
{
	const int MAX = 1000 * 1000;
	primes.clear();
	primes.reserve(10000);
	vector<char> a;
	a.resize(MAX);
	for(int i=2;i<MAX;++i)
		if (a[i] == 0)
		{
			primes.push_back(i);
			for(int j=i+i;j<MAX;j+=i)
				a[j]=1;
		}
}


int main()
{
	initPrimes();
	int m;
	long long a, b, n, c;
	int sig;
	vector<long long> divs;

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

	divs.reserve(100);
	scanf("%d", &m);

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

	return 0;
}