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

#define MAX_PRIME 1e6

using namespace std;

int pinex(const int A, const int B, const vector<int> &primes) {
    int i, k;
    int mid = B / 2;
    vector<int> divisors;

    for (int d : primes) {
        if (B % d == 0) {
            divisors.push_back(d);
        } else if (d > mid) {
            // daca nu s-a gasit niciun divizor pana acum, inseamna ca e prim
            if (divisors.size() == 0)
                divisors.push_back(B);
            break;
        }
    }

    int total = 0;
    int n = divisors.size();
    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 = 0;
    while (i >= 0) {
        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) {
                int prod = 1;
                int no_factors = 0;
                // vad ce elemente sunt in submultimea-solutie gasita
                for (k = 0; k < n; k++) {
                    if (mask[k] == 1) {
                        prod *= divisors[k];
                        ++no_factors;
                    }
                }

                int cardinal = (int) 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) {
    int numbers[N + 1];
    int i, j, k;

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

    int mid = N / 2;
    for (j = 2; j <= mid; 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, 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();
}