#include<cstdio>
#define in "pinex.in"
#define out "pinex.out"
#define MAX 1000002
long long a,b,tot,n,nrp,p[1<<15],pr[1<<10],sol[10];
void ciur()
{
    bool f[MAX]={false};
    for(long long i=2;i<MAX;i++)
        if(!f[i])
        {
            p[++nrp]=i;
            for(long long j=i*i;j<MAX;j+=i)
                f[j]=true;
        }
}
void dfp(long long x)
{
    for(long long i=1;(long long)p[i]*p[i]<=x;i++)
        if(x%p[i]==0)
        {
            pr[++n]=p[i];
            while(x%p[i]==0)
                x/=p[i];
        }
    if(x>1)
        pr[++n]=x;
}
void calc()
{
    long long nrt=1,q=0;
    for(long long i=1;i<=n;i++)
        if(sol[i]==1)
            nrt*=pr[i], q++;
    if(q%2==0 && q)
        tot-=(a/nrt);
    else if(q) tot+=(a/nrt);
}
void back(long long poz)
{
    if(poz>n)
    {
        calc();
        return;
    }
    sol[poz]=0;
    back(poz+1);
    sol[poz]=1;
    back(poz+1);
}
void solve(long long a,long long b)
{
    dfp(b);
    back(1);
    printf("%lld\n",a-tot);
}
void reset()
{
    tot=n=0;
}
void read()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    ciur();
    long long nrn;
    scanf("%lld",&nrn);
    for(long long i=1;i<=nrn;i++)
    {
        scanf("%lld%lld",&a,&b);
        solve(a,b);
        reset();
    }
}
int main()
{
    read();
    return 0;
}