#include <bits/stdc++.h>

#define vt vector
#define pb push_back
#define em emplace
#define emb emplace_back

using ll = long long;
using ull = unsigned long long;
 
using namespace std;
 
inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int LIM = 1e6;

vt <int> primes;

void sieve() {
    vt <bool> marked(LIM + 1);
    for(int i = 2;i <= LIM;i++) 
        if(!marked[i]) {
            primes.emb(i);
            for(int j = 2 * i;j <= LIM;j += i) {
                marked[j] = 1;
            }
        }
}

void solve() {
    ll A, B; cin >> A >> B;

    vt <int> fact;
    for(int d : primes) {
        if(1LL * d * d > B) {
            if(B > 1)
                fact.emb(B); 
            break;
        }

        if(B % d == 0) {
            fact.emb(d);
            while(B % d == 0) {
                B /= d;
            }
        }
    }

    int n = fact.size();
    ll sol = A;
    for(int msk = 1;msk < (1 << n);msk++) {
        ll cnt = 0, prod = 1;

        for(int i = 0;i < n;i++) {
            if(msk & (1 << i)) {
                prod = 1LL * prod * fact[i];
                ++cnt;
            }
        }

        if(cnt % 2) cnt = -1;
        else cnt = 1;

        sol = sol + 1LL * cnt * A / prod;
    }

    cout << sol << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    Open("pinex");

    sieve();
 
    int T; cin >> T;
    for(;T;T--) {
        solve();
    }
 
    return 0;
}