#include <fstream>
#include <math.h>
#define nmax 500

using namespace std;

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

long long sol, a, b;
int v[nmax];
int nr, n;

void div()
{
	nr = 0;
	float val = sqrt(b);
	int d = 2;
	while(b > 1)
	{
		if(b % d == 0)
		{
			v[++nr] = d;
			while(b % d == 0)
				b /= d;
		}
		if(d > val && b > 1)
		{
			v[++nr] = b;
			b = 1;
		}
		if(d == 2) d += 1;
		else d += 2;
	}
}

void calc()
{
	sol = a;
	int i, j;
	for(i = 1; i < (1<<nr); ++ i)
	{
		long long r = 0;
		long long rez = 1;
		for(j = 0; j < nr; ++ j)
			if(i & (1 << j))
			{
				++r;
				rez = 1LL * rez * v[j+1];
			}
		if(r%2) r=-1;
		else r=1;
		sol = sol + 1LL * r * a / rez;
		// sol += (long long) r * a/rez;
	}
}

int main()
{
	int i;
	fin >> n;
	for(i = 1; i <= n; ++ i)
	{
		fin >> a >> b;
		div();
		calc();
		fout << sol << "\n";
	}
	return 0;
}