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

vector<int> primes;

void initPrimes()
{
	primes.clear();
	vector<char> a;
	a.resize(1000001);
	for(int i=2;i<1000000;++i)
		if (a[i] == 0)
		{
			primes.push_back(i);
			for(int j=i+i;j<1000000;j+=i)
				a[i]=1;
		}
}


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

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

	divs.reserve(100);
	cin >> m;

	while (m --)
	{
		cin >> 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 = a;
			sig = 1;
			for(int j=1, k=0; j<=i; j<<=1, ++ k)
				if(i&j)
					c /= divs[k], sig *= -1;
			n += c * sig;
		}
		cout << n << endl;
	}

	return 0;
}