#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

void findPrimes(int aux, std::vector<long long> &primes, std::vector<long long> &found) {
    found = std::vector<long long>();
    for (int prime : primes) {
        if (!(aux % prime)) {
            found.push_back(prime);
        }
        if (prime > (sqrt(aux) + 1)) {
            break;
        }
    }
}

void comp(int a, std::vector<long long> &primes, long long &sum, long long div, int nCount, int ind) {
    if (nCount > 0) {
        sum += pow(-1, nCount - 1) * (a / div);
    }
    for (int i(ind); i < primes.size(); i++) {
        comp(a, primes, sum, div * primes[i], nCount + 1, i + 1);
    }
}

int main() {
    std::ifstream fileIn("pinex.in");
    std::ofstream fileOut("pinex.out");

    std::vector<long long> primes;
    std::vector<bool> ciur(1e6 + 1, true);
    ciur[2] = true;
    for (int i(2); i <= 1e6; i++) {
        if (!ciur[i]) {
            continue;
        }
        primes.push_back(i);
        for (int j(i + i); j <= 1e6; j += i) {
            ciur[j] = false;
        }
    }

    ciur.clear();

    int nO, a, b;
    long long sum;

    fileIn >> nO;

    std::vector<long long> found;
    for (; nO; nO--) {
        fileIn >> a >> b;
        sum = 0;
        findPrimes(b, primes, found);
        comp(a, found, sum, 1, 0, 0);
        fileOut << a - sum << '\n';
    }

    fileIn.close();
    fileOut.close();
    return 0;
}