#include <bits/stdc++.h>

#define llg long long

const llg MAXSIEVE = (1e6) + 5;

llg M, A, B;
std::vector <llg> primes, divs;

bool sieve[MAXSIEVE];
void buildPrimes() {
    for (llg i=2, j; i<MAXSIEVE; ++i)
        if (!sieve[i]) {
            primes.push_back(i);
            for (j=2*i; j<MAXSIEVE; j+=i)
                sieve[j] = 1;
        }
}

void buildDivs() {
    divs.clear();
    llg x = B;
    for (llg i=0; i<primes.size() && x>1; ++i) {
        if (x%primes[i] == 0)
            x /= primes[i], divs.push_back(primes[i]);
    }
}

llg ans;
void calcrecc(llg x = 1, llg idx = 0, llg sgn = 1) {
    ans += (A/x)*sgn;
    if (idx >= divs.size()) return;
    for (llg i=idx; i<divs.size(); ++i)
        if (x*divs[i] <= A)
            calcrecc(x*divs[i], i+1, -sgn);
}

void computePinex() {
    ans = 0;
    calcrecc();
}

std::ifstream input ("pinex.in");
std::ofstream output("pinex.out");

void readInput() {
    input >> A >> B;
}

void solveInput() {
    buildDivs();
    computePinex();
    output << ans << '\n';
}

int main()
{
    buildPrimes();
    input >> M;
    while (M--) {
        readInput();
        solveInput();
    }

    return 0;
}