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

#define MAX_PRIME 1e6

using namespace std;

long long pinex(const long long &A, long long B, const vector<int>
                    &primes) {
    if (B == 1LL) {
        return A;
    }

    long i, k;
    long long threshold = (long long) sqrt((double) B) + 1LL;

    // lista cu cele k multimi de divizori ai lui B
    vector<int> divisors;

    for (int d : primes) {
        if (B % d == 0) {
            divisors.push_back(d);
            while (B % d == 0)
                B /= d;
        } else if (d > threshold) {
            // daca nu s-a gasit niciun divizor pana acum, inseamna ca B e prim
            if (divisors.size() == 0UL) {               
                if (B <= A)
                    return A - ((int) floor((double) A / (double) B));
                else
                    return A;
            }
            // aici am terminat de gasit divizorii B-ului initial;
            // daca B a ramas la o valoare mai mare ca 1, inseamna ca acea
            // valoare reprezinta un divizor prim al sau
            if (B > 1) {
                divisors.push_back(B);
            }
            break;
        }
    }

    const long n = (long) divisors.size();
    long long total = 0LL;
    char mask[n];

    // calculez toate submultimile de multimi generate de divizorii primi ai
    // lui B
    for (k = 0; k < n; k++)
        mask[k] = -1;

    i = 0L;
    while (i >= 0L) {
        bool valid = false;

        while (!valid and mask[i] <= 1) {
            mask[i] = mask[i] + 1;
            valid = (mask[i] >= 0);
        }

        if (mask[i] <= 1) {
            if (i == n - 1) {
                long long prod = 1;
                int no_factors = 0;

                // vad ce elemente sunt in submultimea-solutie gasita
                for (k = 0L; k < n; k++) {
                    if (mask[k] == 1) {
                        prod *= divisors[k];
                        ++no_factors;
                    }
                }

                long cardinal = (long) floor(((double) A) / ((double) prod));

                if (no_factors > 0) {
                    if (no_factors % 2 == 0)
                        total -= cardinal;
                    else
                        total += cardinal;
                }
            } else {
                ++i;
            }
        } else {
            mask[i] = -1;
            i--;
        }
    }

    return A - total;
}

// calculeaza numerele prime mai mici sau egale cu N si le pune in primes
void calculate_primes(int N, vector<int> &primes) {
    char numbers[N + 1];
    int i, j, k;

    for (i = 2; i <= N; i++)
        numbers[i] = 1;

    for (j = 2; j <= N; j++) {
        if (numbers[j] == 1) {
            for (k = (j << 1); k <= N; k += j) {
                numbers[k] = 0;
            }
        }
    }

    for (i = 2; i <= N; i++) {
        if (numbers[i] == 1) {
            primes.push_back(i);
        }
    }
}

int main(void) {
    vector<int> primes;
    primes.reserve(MAX_PRIME);
    calculate_primes(MAX_PRIME, primes);

    int M;
    long long A, B;
    const string INPUT_FILE_NAME = "pinex.in";
    const string OUTPUT_FILE_NAME = "pinex.out";
    ifstream in(INPUT_FILE_NAME);
    ofstream out(OUTPUT_FILE_NAME);

    in >> M;
    for (int i = 0; i < M; i++) {
        in >> A >> B;
        out << pinex(A, B, primes) << "\n";
    }

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

    return 0;
}