#include <cstdio>
#define Bmax 1000000
#define LL long long

using namespace std;

LL a,b,desc[35],n,i;
int nrprim[80005];
bool prim[Bmax+5];

inline void prec()
{
    for (int i=2;i<=Bmax;++i)
    if (!prim[i])
    {
        for (int j=i*2;j<=Bmax;j+=i)
          prim[j]=true;

        nrprim[++nrprim[0]]=i;
    }
}

inline void solve()
{
    LL d,prod,nr,sol;
    d=0; sol=a;
    desc[0]=0;
    while (b>1)
    {
        ++d;
        if (b%nrprim[d]==0)
        {
            desc[++desc[0]]=nrprim[d];
            while (b%nrprim[d]==0)
             b/=nrprim[d];
        }

        if (nrprim[d]*nrprim[d]>b && b>1)
        {
            desc[++desc[0]]=b;
            b=1;
        }

    }


    for (LL i=1;i<(1<<desc[0]);++i)
    {
        nr=0; prod=1;
        for (LL j=0;j<desc[0];++j)
           if ((1<<j)&i)
           {
               prod*=1LL*desc[j+1];
               ++nr;
           }


    if (nr%2==0) nr=1;
     else nr=-1;

    sol+=1LL*nr*a/prod;
    }




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

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

    prec();

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

    return 0;
}