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

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

const int sqrtmax = 1000002;
int M, ciur[sqrtmax];
long long A, B, R, fact[20];

void pre ()
{
    fi >> M;

    int i, j;
    for (i = 2; i < sqrtmax; i++)
    {
        if (ciur[i] == 1)
            continue;

        ciur[++ciur[0]] = i;

        for (j = i << 1; j < sqrtmax; j++)
        {
            ciur[j] = 1;
        }
    }
}

void divizori (long long x)
{
    int sq = sqrt (x), i;
    long long d;
    fact[0] = 0;

    for (i = 1; i <= ciur[0] && ciur[i] <= x; i++)
    {
        d = ciur[i];
        if (x % d == 0)
            fact[++fact[0]] = d;
        while (x % d == 0)
            x /= d;
    }
    if (x != 1)
        fact[++fact[0]] = x;
}

void pinex ()
{
    int s, b;
    long long p, nr;

    for (s = 1; s < 1 << fact[0]; s++)
    {
        p = 1, nr = 0;

        for (b = 0; b < fact[0]; b++)
        {
            if ((s >> b) & 1)
            {
                p *= fact[b + 1];
                nr ++;
            }
        }

        if (nr & 1)
            nr = 1;
        else
            nr = -1;

        R += nr * (A / p);
    }

}

void rez ()
{
    while (M --)
    {
        fi >> A >> B;
        R = 0;
        divizori (B);
        pinex ();
        fo << A - R << '\n';
    }
}

int main ()
{
    pre ();
    rez ();
    return 0;
}