#include <fstream>

#define Nmax 1000100

using namespace std;

int nrDiv, Top, Prime[Nmax / 5], Div[Nmax / 5];
long long A, B, Answer;
bool used[Nmax];

void Solve() {

    int i, Combination, Sign, Total;
    long long Product;

    Answer = A;
    Total = (1 << nrDiv);

    for(Combination = 1; Combination < Total; Combination++) {

        Product = 1;
        Sign = 0;

        for(i = 1; i <= nrDiv; i++)
            if((Combination & (1 << (i-1))) != 0) {
                Product *= Div[i];
                ++Sign;
                }

        if(Sign & 1)
            Answer -= A / Product;
        else
            Answer += A / Product;

        }

}
void Factorise() {

    nrDiv = 0;

    for(int i = 1; 1LL * Prime[i] * Prime[i] <= B; i++)
        if(B % Prime[i] == 0)
            for(Div[++nrDiv] = Prime[i]; B % Prime[i] == 0; B /= Prime[i]);

    if(B > 1)
        Div[++nrDiv] = B;

}
void Sieve() {

    int i, j;

    Prime[++Top] = 2;

    for(i = 3; i < Nmax; i += 2)
        if(!used[i]) {

            Prime[++Top] = i;

            if(i <= 1000)
                for(j = i * i; j < Nmax; j += (i << 1))
                    used[j] = true;

        }

}
int main() {

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

    in >> T;

    Sieve();

    while(T--) {

        in >> A >> B;
        Factorise();
        Solve();

        out << Answer << '\n';

        }

    in.close();
    out.close();

    return 0;

}