#include <fstream>
#include <cmath>
using namespace std;

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

const int MAXB = 100005;//B este pana la 10^12, dar folosim doar sqrt(B)

bool neprim[MAXB];

int prime[80002];


void preprocesare()
{
    for (int i = 2;i * i < MAXB;++i)
        if (!neprim[i])
            for (int j = i * i;j < MAXB;j += i)
                neprim[j] = true;
    for (int i = 2;i < MAXB;++i)
        if (!neprim[i])
            prime[++prime[0]] = i;
}

long long A,B;

void rezolvare()
{
    long long factori[30] = {0};
    long long d = 0;
    while(B > 1)//descompunere in factori primi
    {
        ++d;
        if (B % prime[d] == 0)
        {
            factori[++factori[0]] = prime[d];
            while(B % prime[d] == 0)
                B /= prime[d];
        }

        if (B > 1 && prime[d] > sqrt(B))
        {
            factori[++factori[0]] = B;
            B = 1;
        }
    }

    long long solutie = A;//Din A numere vom scadea cele care sunt neprime cu B

    //generam toate submultimile de factori folosind operatii pe biti
    for (int i = 1;i < (1 << factori[0]);++i)
    {
        char nr = 0;
        long long prodfact = 1;
        for (int j = 0;j < factori[0];++j)
            if (((1 << j) & i) != 0)//elementul j apare in aceasta submultime formata din bitii lui i
            {
                ++nr;
                prodfact *= factori[j + 1];
            }

        if (nr % 2 == 0)//cele cu numar par sunt incluse
            solutie += A / prodfact;
        else//cele cu numar impar sunt excluse
            solutie -= A / prodfact;
    }
    out << solutie << '\n';
}

int main()
{
    preprocesare();
    int nr_teste;
    in >> nr_teste;
    while (nr_teste > 0)
    {
        in >> A >> B;
        rezolvare();
        --nr_teste;
    }
    return 0;
}