#include <bits/stdc++.h>
#define ll long long 
#define MOD 9973

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

int t;
ll a, b;

vector<ll> gen_primes() {
    bitset<1000005> marked;
    vector<ll> primes; 
    int limit = 1000000;

    for (int i = 2; i <= limit; i++) {
        if (!marked[i]) {
            primes.push_back(i);

            for (int j = i + i; j <= limit; j += i) {
                marked[j] = 1;
            }
        }
    }

    return primes;
}

vector<pair<ll, ll> > decompose(ll n, vector<ll> &primes) {
    vector<pair<ll, ll> > ans;
    
    for (auto i : primes) {
        if (i * i > n) {
            break;
        }

        if (n % i) {
            continue;
        }

        ll count = 0;
        while (n % i == 0) {
            count++;
            n /= i;
        }

        ans.push_back({i, count});
    }

    if (n > 1) {
        ans.push_back({n, 1ll});
    }

    return ans;
}

void pinex(int id, vector<pair<ll, ll> > &decomp, ll mask, ll sign, ll &ans, ll limit) {
    if (id == decomp.size()) {
        if (mask != 1) {
            ans += sign * (limit / mask);
        }      

        return;
    }

    if (mask > limit) {
        return;
    }

    auto prime = decomp[id].first;

    pinex(id + 1, decomp, mask * prime, -sign, ans, limit);
    pinex(id + 1, decomp, mask, sign, ans, limit);
}

void solve(vector<ll> &primes) {
    in >> a >> b;

    auto decomp = decompose(b, primes);
    ll ans = 0;

    pinex(0, decomp, 1, -1, ans, a);

    out << a - ans << '\n';
}

int main() {
    auto primes = gen_primes();

    in >> t;
    while (t--) {
        solve(primes);
    }

    return 0;
}