#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e6 + 7;

vector < int > prime;
int sd[N], ndiv;
int deev[20];
long long ans, a;

void precalc() {

    for (int i = 2; i < N; ++i) {
        if (!sd[i])
            sd[i] = prime.size() + 1,
            prime.push_back(i);
        for (int j = 0; j < sd[i] && 1LL * i * prime[j] < N; ++j)
            sd[i * prime[j]] = j + 1;
    }
}

void bkt(int i = 0, int coef = 1, long long prod = 1) {
    if (i == ndiv) {
        ans += coef * (a / prod);
        return;
    }
    bkt(i + 1, coef, prod);
    if (a / prod < deev[i])
        return;
    if (a / deev[i] < prod)
        return;
    if (deev[i] * prod < 0)
        return;
    bkt(i + 1, -coef, prod * deev[i]);
}

int main()
{
    int t;
    long long b;
    precalc();
    cin >> t;
    while (t--) {
        cin >> a >> b;
        ans = 0;
        ndiv = 0;
        for (int i = 0; i < prime.size() && b >= prime[i]; ++i) {
            if (!(b % prime[i])) {
                deev[ndiv++] = prime[i];
                while (!(b % prime[i]))
                    b /= prime[i];
            }
        }
        if (b - 1)
            deev[ndiv++] = b;
        bkt();
        cout << ans << '\n';
    }
    return 0;
}