#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long A;
vector<long long> prime;
long long neprime;

vector<long long> factori_primi(long long B) {
    vector<long long> f;
    for (long long d = 2; d * d <= B; d++) {
        if (B % d == 0) {
            f.push_back(d);
            while (B % d == 0)
                B /= d;
        }
    }
    if (B > 1)
        f.push_back(B);
    return f;
}

void pinex(int pos, long long produs, int cnt) {
    if (pos == prime.size()) {
        if (cnt == 0) return;

        long long val = A / produs;

        if (cnt % 2 == 1)
            neprime += val;
        else
            neprime -= val;

        return;
    }

    pinex(pos + 1, produs, cnt);

    if (produs <= A / prime[pos]) {
        pinex(pos + 1, produs * prime[pos], cnt + 1);
    }
}

int main() {
    int M;
    fin >> M;

    while (M--) {
        long long B;
        fin >> A >> B;

        prime = factori_primi(B);
        neprime = 0;

        pinex(0, 1, 0);

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

    return 0;
}