#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
using LL = long long;
const LL MAX_SIZE = 1E6;
LL res;
bitset<MAX_SIZE + 1> prime;
vector<LL> prime_arr;


void precalc_prime_arr()
{
    prime[0] = prime[1] = 1;
    for (LL i = 2; i * i <= MAX_SIZE; i += 1 + i != 2)
    {
        if (prime[i] == 0)
        {
            for (LL j = i; j <= MAX_SIZE / i; ++j)
            {
                prime[j * i] = 1;
            }
        }
    }

    prime_arr.emplace_back(2);
    for (LL i = 3; i <= MAX_SIZE; i += 2)
    {
        if (!prime[i])
        {
            prime_arr.emplace_back(i);
        }
    }
}


void solve(LL A, LL B)
{
    vector<LL> prime_facs;
    prime_facs.reserve(20);

    int index = 0;
    for (; prime_arr[index] * prime_arr[index] <= B; ++index)
    {
        if (B % prime_arr[index] == 0)
        {
            prime_facs.emplace_back(prime_arr[index]);

            while (B % prime_arr[index] == 0)
            {
                B /= prime_arr[index];
            }
        }
    }
    if (B > 1)
    {
        prime_facs.emplace_back(B);
    }

    LL nr_subsets = 0, cur_product = 1;
    for (LL i = 1; i < (1LL << prime_facs.size()); ++i)
    {
        for (LL j = 0; j < prime_facs.size(); ++j)
        {
            if ((1LL << j) & i)
            {
                cur_product *= prime_facs[j];
                ++nr_subsets;
            }
        }

        LL sign;
        if (nr_subsets % 2 == 0)
        {
            sign = -1;
        }
        else
        {
            sign = 1;
        }

        res += sign * A / cur_product;

        cur_product = 1;
        nr_subsets = 0;
    }
}


int main()
{
    precalc_prime_arr();

    ifstream fin("pinex.in");

    LL M;
    fin >> M;

    ofstream fout("pinex.out");
    while (M--)
    {
        LL A, B;

        fin >> A >> B;
        solve(A, B);

        fout << A - res << "\n";
        res = 0;
    }
}