#include <bits/stdc++.h>

using namespace std;

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

int t;
long long a, b;

int main() {
    in >> t;
    while (t--) {
        in >> a >> b;
        vector <int> primes;
        long long d = 2;
        while (b != 1) {
            if (b % d == 0) {
                primes.emplace_back(d);
                while (b % d == 0)
                    b /= d;
            }
            if (d * d <= b) {
                if (d == 2)
                    ++d;
                else
                    d += 2;
            } else
                d = b;
        }
        int n = (int)primes.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 *= primes[i];
            }
            if (sign & 1)
                rez += a / p;
            else
                rez -= a / p;
        }
        out << a - rez << '\n';
    }
    return 0;
}