#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MAX 1000005
#define DIM 78505
#define LIM 35

int prim[DIM];
ll fact[DIM];
bool v[MAX];
int t,m;
ll a,b;

void ciur ()
{
    int i,j;

    for (i=2; i<MAX; ++i)
        if (!v[i])
        {
            prim[++m]=i;
            for (j=2*i; j<MAX; j+=i)
                v[j]=1;
        }
}

ll solve ()
{
    ll d,nrt,prod;
    int nr,i,j,ok;

    for (nr=0, i=1; prim[i]*prim[i]<=b && i<=m; ++i)
        if (b%prim[i]==0)
            for (fact[++nr]=prim[i]; b%prim[i]==0; b/=prim[i]);
    if (b>1)
            fact[++nr]=b;
    nrt=a;
    for (i=1; i<(1<<nr); ++i)
    {
        for (ok=j=0, prod=1; j<nr; ++j)
            if (i&(1<<j))
            {
                prod*=fact[j+1];
                ok=(ok+1)%2;
            }
        if (ok)
            nrt-=a/prod;
        else
            nrt+=a/prod;
    }
    return nrt;
}

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

    ciur ();
    scanf ("%d",&t);
    for (i=1; i<=t; ++i)
    {
        scanf ("%lld%lld",&a,&b);
        printf ("%lld\n",solve ());
    }

    return 0;
}