#include<bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 ll euler_phi(ll n) {

   ll m = ll(sqrt(n + 0.5));

   ll ans = n;

   for (ll i = ; i <= m; i++)

     if (n % i == ) {

       ans = ans / i * (i - );

       while (n % i == ) n /= i;

     }

   if (n > ) ans = ans / n * (n - );

   return ans;

 }

 ll gcd(ll a, ll b) {

   if (b == ) return a;

   return gcd(b, a % b);

 }

 int main()

 {

     int t;

     cin>>t;

     while(t--){

         ll a,m;

         cin>>a>>m;

         m=m/gcd(a,m);

         ll x = euler_phi(m);

         cout<<x<<endl;

     }

     return ;

 }