#include <iostream> // sterge
#include <fstream>
#include <math.h>
using namespace std;

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

long long nr, a, b, vf, fact[50], viz[50], v[50], res;

void generare(int poz)
{
    long long sign = 1, produs;

    if (poz == vf + 1)
        return ;
    if (poz % 2 == 0)
        sign = -1;
    for (int i = v[poz - 1] + 1; i <= vf; i++)
        if (viz[i] == 0) {
            viz[i] = 1;
            v[poz] = i;
            produs = 1;
            for (int i = 1; i <= poz; i++)
                produs = produs * fact[v[i]];
            produs = a / produs;
            res = res + produs * sign;
            generare(poz + 1);
            viz[i] = 0;
        }
}

void pinex()
{
    long long d = 2;

    vf = 0;
    while (b > 1) {
        if (b % d == 0) {
            fact[++vf] = d;
            while (b % d == 0)
                b = b / d;
        }
        if (d > sqrt(b) && b > 1) {
            fact[++vf] = b;
            b = 1;
        }
        if (d == 2)
            d++;
        else
            d = d + 2;
    }
    res = 0;
    generare(1);
}

int main()
{
    fin >> nr;
    for (int i = 0; i < nr; i++) {
        fin >> a >> b;
        pinex();
        fout << a - res << '\n';
    }
    return 0;
}