#include <iostream>
#include <fstream>
#include <vector>
// AMAX = 10^18, BMAX = 10^12
#define NMAX 1000000 // 10^6 * 10^6 = 10^12

using namespace std;
using ll = long long;

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

int M;
bool ciur[NMAX + 1];
vector <int> primes;
vector <ll> factB;

void genPrime()
{
    ciur[1] = 1;

    for (int i = 4; i <= NMAX; i += 2) ciur[i] = 1;

    for (int d = 3; d * d <= NMAX; d += 2)
        if (ciur[d] == 0)
            for (int i = d * d; i <= NMAX; i += d)
                ciur[i] = 1;

    for (int i = 2; i <= NMAX; ++i)
        if (ciur[i] == 0)
            primes.push_back(i);
}

void descInFactPrimi(ll b)
{
    // descompun pe b in factori primi
    int i = 0;

    factB.clear();

    while (i < primes.size() && 1LL * primes[i] * primes[i] <= b) {
        if (b % primes[i] == 0) {
            factB.push_back(primes[i]);
            while (b % primes[i] == 0)
                b /= primes[i];
        }
        ++i;
    }
    if (b > 1) factB.push_back(b);
}

void calc(ll a)
{
    int powDivPrimi = (1 << (int)factB.size());
    int divPrimi = factB.size();

    ll suma = 0;
    ll produs, semn;

    for (int mask = 0; mask < powDivPrimi; ++mask) {
        produs = 1;
        semn = 0;
        for (int i = 0; i < divPrimi; ++i) {
            if (mask & (1 << i)) {
                produs *= factB[i];
                ++semn;
            }
        }
        if (semn & 1) suma -= a / produs;
        else suma += a / produs;
    }

    fout << suma << '\n';

}

int main()
{
    ll a, b;

    fin >> M;

    genPrime();

    while (M--) {
        fin >> a >> b;
        descInFactPrimi(b);
        calc(a);
    }

    fin.close();
    fout.close();
    return 0;
}