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

typedef long long ll;

vector<ll> fact(ll n) {
    vector<ll> f;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            f.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) f.push_back(n);
    return f;
}

int main() {
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");

    int M;
    fin >> M;

    while (M--) {
        ll A, B;
        fin >> A >> B;

        vector<ll> primes = fact(B);
        int k = primes.size();

        ll bad = 0;

        for (int mask = 1; mask < (1 << k); mask++) {
            ll prod = 1;
            int bits = 0;

            for (int i = 0; i < k; i++) {
                if (mask & (1 << i)) {
                    prod *= primes[i];
                    bits++;
                }
            }

            ll cnt = A / prod;

            if (bits % 2) bad += cnt;
            else bad -= cnt;
        }

        fout << A - bad << "\n";
    }

    return 0;
}