#include <bits/stdc++.h>

using namespace std;

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

int t;
bool f[1000001];
long long a, b;
vector <int> primes;

inline void ciur(int n) {
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!f[i]) {
            primes.emplace_back(i);
            for (int j = i; j <= n; j += i)
                f[j] = 1;
        }
    }
}

int main() {
    in >> t;
    ciur(1e6);
    while (t--) {
        in >> a >> b;
        vector <int> div;
        int poz = 0;
        while (b != 1) {
            if (b % primes[poz] == 0) {
                div.emplace_back(primes[poz]);
                while (b % primes[poz] == 0)
                    b /= primes[poz];
            }
            ++poz;
        }
        int n = (int)div.size();
        long long rez = 0;
        for (long long msk = 1; msk < (1 << n); ++msk) {
            long long p = 1;
            int sign = __builtin_popcount(msk);
            for (int i = 0; i < n; ++i) {
                if (msk & (1 << i))
                    p *= div[i];
            }
            if (sign & 1)
                rez += a / p;
            else
                rez -= a / p;
        }
        out << a - rez << '\n';
    }
    return 0;
}