include[HTML_REMOVED]
using namespace std;
int T;
long long a,b;
void f(long long x)
{
long long ans=x;
for(long long i=2;ii<=x;i++)
{
if(x%i==0) ans=ans/i(i-1);
while(x%i==0) x/=i;
}
if(x!=1) ans=ans/x*(x-1);
cout<[HTML_REMOVED]>T;
while(T–)
{
long long a,b;
cin>>a>>b;
long long t=__gcd(a,b);
b/=t;
f(b);
}
return 0;
}