#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;
}