#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a, ll b){
    if(a==0||b==0) return a+b;
    if(a==b) return a;
    return gcd(b,a%b);
}
ll phi(ll n){
    ll ans = n; 
    ll d = 2,dem;
    while(d*d<=n){
        dem = 0;
        while(n%d==0){
            n/=d;
            dem++;
        }
        if(dem>0) ans-=ans/d;
        d++;
    }
    if(n>1) ans-=ans/n;
    return ans;
}
int main(){
    ll a,b,d,t;
    cin>>t;
    while(t--){
    cin>>a>>b;
    d=gcd(a,b);
    cout<<phi(b/d)<<'\n';
    }
    return 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKbGwgZ2NkKGxsIGEsIGxsIGIpewogICAgaWYoYT09MHx8Yj09MCkgcmV0dXJuIGErYjsKICAgIGlmKGE9PWIpIHJldHVybiBhOwogICAgcmV0dXJuIGdjZChiLGElYik7Cn0KbGwgcGhpKGxsIG4pewogICAgbGwgYW5zID0gbjsgCiAgICBsbCBkID0gMixkZW07CiAgICB3aGlsZShkKmQ8PW4pewogICAgICAgIGRlbSA9IDA7CiAgICAgICAgd2hpbGUobiVkPT0wKXsKICAgICAgICAgICAgbi89ZDsKICAgICAgICAgICAgZGVtKys7CiAgICAgICAgfQogICAgICAgIGlmKGRlbT4wKSBhbnMtPWFucy9kOwogICAgICAgIGQrKzsKICAgIH0KICAgIGlmKG4+MSkgYW5zLT1hbnMvbjsKICAgIHJldHVybiBhbnM7Cn0KaW50IG1haW4oKXsKICAgIGxsIGEsYixkLHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pewogICAgY2luPj5hPj5iOwogICAgZD1nY2QoYSxiKTsKICAgIGNvdXQ8PHBoaShiL2QpPDwnXG4nOwogICAgfQogICAgcmV0dXJuIDA7Cn0=

Mwo0IDkKNSAxMAo0MiA5OTk5OTk5OTY3

3
4 9
5 10
42 9999999967