#include<bits/stdc++.h>
using namespace std;
long long n,m,t,k=0,a,l,p;    
int main()
{
    cin>>t;
    while(t--)
	{
        cin>>a>>m;
        n=m/__gcd(a,m); 
		k=n;
        for(long long i=2;i*i<=n;i++)
		{
            if(n%i==0)
			{
                k/=i; 
				k*=(i-1);
                while(n%i==0)
				{
					n/=i;
				}
            }
        }
        if(n!=1)
		k-=k/n;
        cout<<k<<endl;
    }
    return 0;
}
 	 	 		  	   			 	 		  		 	 	