#include<fstream>
using namespace std;
int t;
int k, n, x[65],s[65], p[65];
int a,b,sum;
ifstream f("pinex.in");
ofstream g("pinex.out");

void prelsol()
{
	if(s[n])
	{
	int pb = 1;
	for(int i = 1; i <= n; ++i)
		if(x[i]) pb *= p[i];
	if(s[n] % 2) 
		sum = sum - a / pb; 
	else 
		sum = sum + a/pb;
	}
}
void back()
{
	k = 1; x[k]= -1;
	do
	{
		while(x[k] < 1)
		{
			x[k]++; s[k] = s[k -1] + x[k];
			if(k == n) prelsol();
			else x[++k] = -1;
		}
		k--;
	}
	while(k);
}
int main()
{	f>>t;
	while(t--)
	{	f>>a>>b;
		sum=a;
		n = 0;
		int d = 2;
		while(d * d <= b)
		{
			if(!(b % d))
			{
				p[++n] = d;
				while(!(b % d)) b /= d;
			}
			d++;
		}
		if(b > 1)
			p[++n] = b;
		back();
		g<<sum<<"\n";
	}
	g.close();
	return 0;
}