#include <fstream>
#include <vector>

#define NMAX 1000005

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

int questions;
unsigned long long int a, b, answerNow;
bool ciur[NMAX];
vector <int> primes;
vector <long long int> divs;

void getCiur() {
    ciur[0] = 1;
    ciur[1] = 1;

    for (int i = 2; i <= NMAX; i++) {

        if (!ciur[i]) {

            primes.push_back(i);

            for (int j = i; j <= NMAX / i; j++)
                ciur[i * j] = 1;
        }
    }
}

void getDiv(long long int x) {

    divs.clear();

    for (int i = 0; i < primes.size() && primes[i] * primes[i] <= x; i++) {

        if (x % primes[i] == 0) {

            divs.push_back(primes[i]);

            while (x % primes[i] == 0)
                x = x / primes[i];
        }
    }

    if (x > 1)
        divs.push_back(x);
}

void backTrack(int poz, long long int val, int last) {

    if (poz > 0) {

        if (poz % 2 == 0)
            answerNow = answerNow - a / val;
        else
            answerNow = answerNow + a / val;
    }

    for (int i = last + 1; i < divs.size(); i++) {

        val = val * divs[i];
        backTrack(poz + 1, val, i);
        val = val / divs[i];
    }
}

int main()
{
    getCiur();

    f >> questions;

    while (questions--) {
        f >> a >> b;

        answerNow = 0;
        getDiv(b);
        backTrack(0, 1, -1);

        g << a - answerNow << "\n";
    }

    return 0;
}