using namespace std;
#include<fstream>
#define MAX_S 1000000
#define ll long long
int fact[80002], N;
int T;
int f[30];
char u[MAX_S];
void eratostene()
{
	int i,j;
	fact[++N] = 2;
	for(i=2;i<MAX_S; i+=2) u[i] = 1;
	for(i = 3; i < MAX_S; i+=2)
	{
		if(u[i] != 1)
		{
			fact[++N] = i;
			for(j = i+i; j < MAX_S; j+=i)
				u[j] = 1;
		}
	}
}
ll solve(ll A, ll B)
{
	ll K = 0, i,j,nr, p, tmp;
	ll sol = 0;
	for( i = 1; fact[i]*fact[i] <= B; ++i)
	{
		if(B%fact[i] == 0)
		{
			f[++K] = fact[i];
			for(;B%fact[i]==0;B/=fact[i]);
		}
	}
	if(B>1) f[++K] = B;
	for(i = 1; i < (1<<K); ++i)
	{
		for(j = 0, nr = 0,p = 1; j < K; ++j)
			if( (1<<j)&i )			
				p = 1LL * p * f[j+1], ++nr;			
		if(nr&1) tmp = 1;
		else tmp = -1;
		sol = sol + 1LL * tmp * ( A / p );
	}
	return A - sol;
}
int main()
{
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	eratostene();
	f>>T; ll A,B;
	while(T--)
	{
		f>>A>>B;
		g<<solve(A,B)<<"\n";
	}
	return 0;
}