#include<stdio.h>
#include<assert.h>
#include<math.h>

int u,m,pr[1000100],lpr[1001000];
long long pa[22],a[501],b[501],sol[501];

void read()
{
    assert(freopen("pinex.in","r",stdin)!=NULL);
    scanf("%d",&m);
    int i;
    for(i=1;i<=m;++i)
        scanf("%lld%lld",&a[i],&b[i]);
}

void count(int k)
{
    int i,j,lim,x,l;
    long long t,p;
    t=a[k];
    lim=1<<pa[0];
    for(i=1;i<lim;++i)
    {
        p=1;
        x=0;
        for(j=1,l=1;j<lim;j<<=1,++l)
            if(i&j)
            {
                p*=pa[l];
                x++;
            }
        if(x%2==0)
            t+=a[k]/p;
        else
            t-=a[k]/p;
    }
    sol[k]=t;
}

void solve()
{
    int i,j,l=1000;
    for(i=2;i<=l;++i)
        if(pr[i]==0)
            for(j=i*i;j<=1000000;j+=i)
                pr[j]=1;
    for(i=2;i<=1000000;++i)
        if(pr[i]==0)
            lpr[++u]=i;
    for(i=1;i<=m;++i)
    {
        for(j=1;j<=u;++j)
            if(b[i]%lpr[j]==0)
            {
                pa[++pa[0]]=lpr[j];
                while(b[i]%lpr[j]==0)
                    b[i]/=lpr[j];
            }
        if(b[i]>1)
            pa[++pa[0]]=b[i];
        count(i);
        for(j=1;j<=pa[0];++j)
            pa[j]=0;
        pa[0]=0;
    }
}

void write()
{
    assert(freopen("pinex.out","w",stdout)!=NULL);
    int i;
    for(i=1;i<=m;++i)
        printf("%lld\n",sol[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}