#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

#define AMAX 1000000000000000010
#define BMAX 1000000000010
#define SQRTBMAX 1000010

vector <long long> prime, factori;
bool ciur[5 * SQRTBMAX];
long long A, B, T;

inline void fciur () {
    long long d = 2;
    ciur[0] = ciur[1] = 1;
    while (d < SQRTBMAX) {
        prime.push_back (d);
        for (long long i = d * d; i < SQRTBMAX; i+= d) {
            ciur[i] = 1;
        }

        d++;
        while (ciur[d]) {
            d++;
        }
    }
}

inline void descomp (int X) {
    int f = 0;
    int cx = X;
    while (prime[f] * prime[f] <= X && X > 1 && f < prime.size()) {
        if (X % prime[f] == 0) {
            factori.push_back (prime[f]);
        }

        while (X % prime[f] == 0) {
            X /= prime[f];
        }

        f++;
    }

    if (X > 1) {
        factori.push_back (X);
    }
}

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

int main () {

    fciur ();

    fin >> T;
    while (T --) {
        fin >> A >> B;
        factori.erase(factori.begin (), factori.end ());
        descomp (B);

        long long ans = A;
        for (int i = 1; i < (1 << factori.size()); i++) {
            long long prod = 1, nr = 0;;

            for (int j = 0; j < factori.size (); j++) {
                if (i & (1 << j)) {
                    prod *= factori[j];
                    nr++;
                }
            }

            if (nr % 2 == 0) {
                ans = ans + A / prod;
            }
            else {
                ans = ans - A / prod;
            }

        }

        fout << ans << '\n';
    }

    return 0;
}