#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <cstring>
#include <climits>
#include <iomanip>
#include <stack>
#include <cstdio>

#define NMAX 1000003
using namespace std;

int n;
unsigned long long int a, b, cartezMult;
bool ciur[NMAX];
vector<long long int>prime;
vector<long long int>diviz;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

void eratostene()
{
	ciur[1] = true;
	ciur[0] = true;
	for (int i = 2; i < NMAX; i++)
	{
		if (!ciur[i])
		{
			prime.push_back(i);
			for (int j = 2; j <= NMAX / i; j++)
			{
				ciur[i * j] = true;
			}
		}
	}
}

void divPrimi(long long int val)
{
	diviz.clear();

	for (int i = 0; i < prime.size() && prime[i] * prime[i] <= val; i++)
	{
		if (val % prime[i] == 0)
		{
			diviz.push_back(prime[i]);
			while (val % prime[i] == 0)
			{
				val /= prime[i];
			}
		}
	}
	if (val > 1)
	{
		diviz.push_back(val);
	}
}

void backtrack(int indexMult, long long int divizorComun, int pozUltimAdaugat)
{
	//imi generez prin backtracking divizorii numarului a
	if (indexMult > 0)
	{
		if (indexMult % 2 == 0)
		{
			//scad
			cartezMult = cartezMult - a / divizorComun;
		}
		else {
			cartezMult = cartezMult + a / divizorComun;
		}

	}
	for (int i = pozUltimAdaugat + 1; i < diviz.size(); i++)
	{
		divizorComun = divizorComun * diviz[i];
		backtrack(indexMult + 1, divizorComun, i);
		divizorComun /= diviz[i];
	}
}

int main()
{
	eratostene();

	fin >> n;
	for (int i = 1; i <= n; i++)
	{

		fin >> a >> b;

		cartezMult = 0;
		divPrimi(b);
		backtrack(0, 1, -1);
		fout << a - cartezMult << "\n";
	}
	return 0;
}