# include <fstream>
# include <bitset>

using namespace std;

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

typedef unsigned long long ULL;
typedef unsigned int UI;

const int LIM = 1100000; // preprocesam nr prime pana la 10^6 + 10^5
const int TNR = 90000; // sunt ~85k nr prime
const int MAX = 200; // 10^12 are 168 de divizori

ULL D[MAX];
ULL P[TNR];

void ciur();
ULL pinex(ULL a, ULL b);

ULL T, a, b;

int main() {
    ciur();

    for (fin >> T; T; --T) {
        fin >> a >> b;
        fout << a - pinex(a, b) << "\n";
    }

    return 0;
}

void ciur() {
    bitset<LIM> v;
    UI k = 0;

    P[++k] = 2;

    for (ULL i=3; i<LIM; i+=2) {
        if (v[i] == 0) {
            P[++k] = i;
            for (ULL j=i+i; j<LIM; j+=i) {
                v[j] = 1;
            }
        }
    }

    P[0] = k;
}

ULL pinex(ULL a, ULL b) {
    bitset<MAX> v;
    ULL finAns = 0, prodDiv = 0;
    UI tmpNr = 0, k = 0, i = 0;

    for (ULL d=1; P[d]<=b && d<=P[0]; d++) {
        if (b % P[d] == 0) {
            D[++k] = P[d];
            while (b % P[d] == 0)
                b /= P[d];
        }
    }

    if (b != 1)
        D[++k] = b;

    while (v[0] == 0) {
        i = k;
        while (v[i] == 1) {
            v[i] = 0;
            i--;
        }
        v[i] = 1;

        tmpNr = 0;
        prodDiv = 1;
        for (i=1; i<=k; i++)
            if (v[i] == 1) {
                tmpNr++;
                prodDiv *= D[i];
            }

        if (tmpNr > 0) {
            if (prodDiv != 0)
                prodDiv = a/prodDiv;

            if ((tmpNr - 1) % 2 == 1)
                prodDiv *= (-1);

            finAns += prodDiv;
        }
    }

    return finAns;
}