#include <bits/stdc++.h>

#define llg long long

const int MAXSIEVE = (1e6) + 5;

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

bool sieve[MAXSIEVE];
void buildPrimes() {
    for (int 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 (int i=0; i<primes.size() && x > 1; ++i) {
        if (x%primes[i] == 0)
            x /= primes[i], divs.push_back(primes[i]);
    }   if (x > 1) divs.push_back(x);
}

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

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;
}