#include "bits/stdc++.h"
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
const int MAX_SQRT_NR = 1e6;


int main()
{
    bitset<MAX_SQRT_NR + 1> is_prime = move(bitset<MAX_SQRT_NR + 1>{}.set());
    vector<int> primes{2};

    auto eratosthenes = [&]() -> void
    {
        is_prime[0] = is_prime[1] = false;
        for (int j = 4; j <= MAX_SQRT_NR; j += 2)
        {
            is_prime[j] = false;
        }

        int i;
        for (i = 3; i * i <= MAX_SQRT_NR; i += 2)
        {
            if (is_prime[i])
            {
                primes.emplace_back(i);
                for (int j = i * i; j <= MAX_SQRT_NR; j += i)
                {
                    is_prime[j] = false;
                }
            }
        }

        for (i += !(i & 1); i <= MAX_SQRT_NR; i += 2)
        {
            if (is_prime[i])
            {
                primes.emplace_back(i);
            }
        }
    };

    eratosthenes();

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

    int M;
    cin >> M;

    while (M--)
    {
        ll A, B;
        cin >> A >> B;

        static auto inc_exc = [&primes](const ll A, ll B) -> ll
        {
            vector<int> prime_divs_B;
            for (const ll prime : primes)
            {
                if (prime * prime > B)
                {
                    break;
                }

                if (B % prime == 0)
                {
                    prime_divs_B.emplace_back(prime);
                    do
                    {
                        B /= prime;
                    } while (B % prime == 0);
                }
            }
            if (B > 1)
            {
                prime_divs_B.emplace_back(B);
            }

            const int omega = prime_divs_B.size();
            ll res{};
            for (int i = 1; i < (1 << omega); ++i)
            {
                ll cur_intersection{1};
                int nr_subsets{};
                for (int j = 0; j < omega; ++j)
                {
                    if (i & (1 << j))
                    {
                        cur_intersection *= prime_divs_B[j];
                        ++nr_subsets;
                    }
                }

                const int sign = nr_subsets & 1 ? 1 : -1;
                res += A / (sign * cur_intersection);
            }

            return res;
        };

        cout << A - inc_exc(A, B) << "\n";
    }
}