#include <iostream>
#include <fstream>

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

int a, b, sub, op[100];
int n, i, S, j, nr, k, m, p[80000], d[100], nrd, nrp=78498;
bool vad[1000000];

void calcul () {
	
	int pro = 1;
	for (int j = 1; j <= k; j++)
		pro *= d[op[j]];
	sub += a/pro;
}

void back (int p)
{
	if (p == k+1)	calcul();
	else 
	{
		for (int i = op[p-1]+1; i <= nrd; i++)
		{
			op[p] = i;
			back(p+1);
		}
	}
}

int main () {
	
	for (i = 2; i <= 1000000; i++)
		if (vad[i] == 0)
		{
			nr++;	p[nr] = i;
			for (j = 2; j*i <= 1000000; j++)
				vad[i*j] = 1;
		}
	
	fin >> m;
	while (m)
	{
		fin >> a >> b;
		nrd = 0;
		nr = 1;
		while (b > 1 && nr <= nrp)
		{
			k = 0;
			while (b%p[nr] == 0)	
			{
				b /= p[nr];		k = 1;
			}
			if (k == 1)	
			{
				nrd++;	d[nrd] = p[nr];
			}
			nr++;
		}
		
		S = a;
		int p = 0;
		for (i = 1; i <= nrd; i++)
		{
			k = i;
			sub = 0;
			back(1);
			
			if (p == 0) {	S -= sub;	p = 1;	}
			else 		{	S += sub;	p = 0;	}
		}
		fout << S << "\n";
		m--;
	}
}