# include <fstream>
# include <bitset>

using namespace std;

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

const int LIM = 1e6+2*1e5+9*1e4; // preprocesam nr prime pana la 1290000
const int TNR = 1e5; // sunt 78498 nr prime
const int MAX = 200; // 1e12 are 168 de divizori
int D[MAX];
int P[TNR];

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

int 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;
    int k = 0;

    P[++k] = 2;

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

    P[0] = k;
}

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

    for (int d=1; P[d]<=b; d++)
        if (b % P[d] == 0)
            D[++k] = P[d];

    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;
}