#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

long long a, b, sol;
bool prime[1000001];
int t, st[15], primes[100000];

void preprocess_primes() {
    int M = 1e6;
    for (int i = 2; i <= M; ++i) prime[i] = true;

    for (int k = 2; k <= M / 2; ++k) {
        if (prime[k])
            for (int i = k + k; i <= M; i += k) prime[i] = false;
    }

    for (int i = 2; i <= M; ++i) {
        if (prime[i]) primes[++primes[0]] = i;
    }
}

void find_prime_divs(int b, int *d) {
    int i = 1;
    while (b != 1) {
        if (b % primes[i] == 0) {
            d[++d[0]] = primes[i];
            do {
                b /= primes[i];
            } while (b % primes[i] == 0);
        }
        i++;
    }
}

void add_solution(int k, int *d) {
    long long p = 1;
    for (int i = 1; i <= k; ++i) p *= d[st[i]];

    if (k % 2 == 0) {
        sol -= a / p;
    } else {
        sol += a / p;
    }
}

void generate(int k, int *d) {
    for (int i = k; i <= d[0]; ++i) {
        if (i <= st[k - 1]) continue;
        st[k] = i;
        add_solution(k, d);
        generate(k + 1, d);
    }
}


int main() {
    in >> t;

    preprocess_primes();

    while (t--) {
        int *d = new int[15]();
        in >> a >> b;
        sol = 0;

        find_prime_divs(b, d);

        generate(1, d);

        out << a - sol << '\n';
    }
}