#include <fstream>
#include <vector>

using namespace std;

/// 100p
const int MAXP = 10000000;  // Margine superioară pentru cel mai mare număr prim

int M;  // Datele de intrare
long long int A, B;

bool v[MAXP + 1];        // Vector pentru Ciurul lui Eratostene
vector<int> prim;        // Vectorul numerelor prime
vector<long long> p;     // Vectorul divizorilor primi ai lui B

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

void generareNumerePrime(int n) {
    int i, j;
    for (i = 3; i * i <= n; i += 2) {
        if (v[i] == 0) {
            for (j = i * i; j <= n; j += 2 * i)
                v[j] = 1;
        }
    }
    prim.push_back(2);
    for (i = 3; i <= n; i += 2) {
        if (v[i] == 0)
            prim.push_back(i);
    }
}

void generareDivizoriB() {
    p.clear();
    for (int i = 0; 1LL * prim[i] * prim[i] <= B; i++) {
        if (B % prim[i] == 0) {
            p.push_back(prim[i]);
            do {
                B /= prim[i];
            } while (B % prim[i] == 0);
        }
    }
    if (B > 1) p.push_back(B);
}

void calcSol() {
    int nt = 1 << p.size();
    long long int card = 0, prod, t;
    for (int i = 1; i < nt; i++) {
        prod = 1;
        int j = 0, p2, ndiv = 0;
        while ((p2 = 1 << j) <= i) {
            if (p2 & i) {
                prod *= p[j];
                ndiv++;
            }
            j++;
        }
        t = A / prod;
        if (ndiv % 2 == 0)
            card -= t;
        else
            card += t;
    }
    g << A - card << '\n';
}

int main() {
    generareNumerePrime(MAXP);
    f >> M;
    while (M--) {
        f >> A >> B;
        generareDivizoriB();
        calcSol();
    }
    f.close();
    g.close();
    return 0;
}