#include <bits/stdc++.h>

using namespace std;

#define MAX_P 1000000
#define MAX_FACTORS 30
typedef long long ll;

// Global variables
ll M, A, B;
ll prime_factors[MAX_FACTORS]; // To store prime factors of B
int small_primes[80000];       // List of small primes
bool is_prime[MAX_P];          // Sieve array

// Precompute all primes less than MAX_P using Sieve of Eratosthenes
void precalculate_primes() {
    fill(is_prime + 2, is_prime + MAX_P, true);

    for (int i = 2; i < MAX_P; i++) {
        if (is_prime[i]) {
            for (int j = 2 * i; j < MAX_P; j += i)
                is_prime[j] = false;
            small_primes[++small_primes[0]] = i;
        }
    }
}

// Applies Inclusion-Exclusion Principle to count numbers in [1, A]
// that are divisible by at least one prime factor of B
void solve() {
    int num_factors = 0;
    int prime_index = 0;

    // Factorize B using the list of small primes
    while (B > 1) {
        prime_index++;

        if (B % small_primes[prime_index] == 0) {
            prime_factors[++num_factors] = small_primes[prime_index];
            while (B % small_primes[prime_index] == 0)
                B /= small_primes[prime_index];
        }

        // If the current prime is larger than sqrt(B) and B is still > 1,
        // then B itself is a prime number
        if (small_primes[prime_index] > sqrt(B) && B > 1) {
            prime_factors[++num_factors] = B;
            B = 1;
        }
    }

    // Apply inclusion-exclusion to count numbers ≤ A that are NOT divisible by any of B’s prime factors
    ll result = A;
    for (int mask = 1; mask < (1 << num_factors); mask++) {
        ll product = 1;
        int bits_set = 0;

        for (int j = 0; j < num_factors; j++) {
            if (mask & (1 << j)) {
                product *= prime_factors[j + 1];
                bits_set++;
            }
        }

        // Inclusion-Exclusion:
        // Subtract or add depending on the number of primes in the subset
        if (bits_set % 2 == 1)
            result -= A / product;
        else
            result += A / product;
    }

    printf("%lld\n", result);
}

int main() {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout); 
    precalculate_primes();
    // Example input
    scanf("%lld", &M);
    while (M--) {
        scanf("%lld %lld", &A, &B);
        memset(prime_factors, 0, sizeof(prime_factors));
        solve();
    }
    return 0;
}