#include <fstream>

using namespace std;

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

const int NP = 1e6;

bool marked[NP];
long long prime[80000], fact[30];
long long A, B;
int T;

void Prec() {
    prime[++prime[0]] = 2;
    for (int i = 3; i <= NP; i += 2) {
        if (!marked[i]) {
            for (int j = 3*i; j < NP; j += 2*i) {
                marked[j] = 1;
            }
            prime[++prime[0]] = i;
        }
    }
}

void Solve(long long A, long long B) {
    int f = 0;
    while (B > 1) {
        for (int i = 1; i <= prime[0] && prime[i]*prime[i] <= B; ++i) {
            if (B % prime[i] == 0) {
                fact[++f] = prime[i];
                while (B % prime[i] == 0)
                    B /= prime[i];
            }
        }
        if (B > 1) {
            fact[++f] = B;
            B = 1;
        }
    }

    long long alt = 0;
    for (int i = 1; i < (1 << f); ++i) {
        long long nr = 0, dn = 1;
        for (int j = 0; j < f; ++j) {
            if ((1 << j) & i) {
                dn *= 1LL * fact[j+1];
                nr++;
            }
        }
        (nr & 1) ? nr = 1 : nr = -1;

        alt += 1LL * nr * A / dn;
    }
    out << A - alt << '\n';

}

int main()
{
    Prec();

    in >> T;
    while (T) {
        in >> A >> B;
        T--;
        Solve(A, B);
    }

    return 0;
}