Educational_Codeforces_Round_81(Rated_for_Div. 2)_D题

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
int T;
LL a,m;

void solve(){
    cin >> a >> m;
    LL n = m/__gcd(a, m);
    LL ans = n;
    for(int i = 2; i <= n/i; ++i){
        if(n%i == 0){
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    cout << ans << endl;
}

int main(){
   // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}