#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}
const int N = 2e5+10;
vector<ll>p;
bool vis[N];

void Init(){
    for(ll i=2;i<N;++i){
        if(!vis[i])p.push_back(i),vis[i]=1;
        for(ll v:p){
            if(i*v>=N)break;
            vis[i*v]=1;
            if(i%v==0)break;
        }
    }
}
ll calc(ll x){
    bool sus=0;
    ll ans=x;
    for(ll v:p){
        if(v*v>x)break;
        if(x%v)continue;
        sus=1;ans=ans/v;ans=ans*(v-1);
    }
    if(!sus)return x-1;
    return ans;
}
int main(){
    int T;scanf("%d",&T);
    Init();
    while(T--){
        ll a,m;scanf("%lld%lld",&a,&m);ll k=gcd(a,m);
        printf("%lld\n",calc(m/k));
    }
    
    return 0;
}