#include <cstdio>

#define LL long long

#define Vmax 1000010

using namespace std;

LL m , A , B;
LL pm[Vmax/7] , div[100];

bool ok[Vmax];

void ciur()
{
    for (LL i = 2; i * i <= Vmax; ++i)
     for (LL j = i * 2; j <= Vmax && !ok[i]; j += i)
      ok[j] = true;

    for (LL i = 2; i <= Vmax; ++i)
     if (!ok[i]) pm[++pm[0]] = i;
}

void make_div(LL n)
{
    div[0] = 0;

    for (LL i = 1; B > 1; ++i)
     if (B % pm[i] == 0)
    {
        div[++div[0]] = pm[i];

        while (B % pm[i] == 0) B /= pm[i];
    }
}

LL solve()
{
    make_div(B); LL sol = 0;

    for (LL x = 1; x < (1 << div[0]); ++x)
    {
        LL cnt = 0 , multiplu = 1;

        for (LL i = 0; i < div[0]; ++i)
         if (x >> i & 1) multiplu *= div[i+1] , cnt++;

        sol += (cnt & 1) ? A / multiplu : (-1) * A / multiplu;
    }

    return A - sol;
}


int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%lld", &m);

    ciur();

    for ( ; m ; --m)
    {
        scanf("%lld %lld", &A, &B);

        printf("%lld\n", solve());
    }


    return 0;
}