#include<stdio.h>
#define prmax 1000000
#define nrpmax 100000
int nr,nrd;
long long a,b,sol;
bool prime[prmax];
int p[nrpmax],divp[16];

void ciur()
{
    int i,j;
    p[nr=1]=2;
    for(i=4; i<=prmax; i+=2)
        prime[i]=1;
    for(i=3; i<=prmax; i++)
        if(!prime[i])
        {
            p[++nr]=i;
            if(i>1000)
                continue;
            for(j=i*i; j<=prmax; j=j+i+i)
                prime[j]=1;
        }
}

void div_b()
{
    int div=1,nr;
    nrd=0;
    while(b>1 && (long long)p[div]*p[div]<=b)
    {
        nr=0;
        while(b%p[div]==0)
        {
            nr++;
            b=b/p[div];
        }
        if(nr)
            divp[++nrd]=p[div];
        div++;
    }
    if(b>1)
        divp[++nrd]=b;
}

int nr_bit(int x)
{
    int nr=0;
    while(x)
    {
        nr++;
        x=x&(x-1);
    }
    return nr;
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    int t,i,j,lim;
    long long prod;
    scanf("%d",&t);
    while(t--)
    {
        sol=0;
        scanf("%lld%lld",&a,&b);
        div_b();
        lim=1<<nrd;
        for(i=0; i<lim; i++)
        {
            nr=nr_bit(i);
            prod=(nr&1)?-1:1;
            for(j=0; j<nrd; j++)
                if(i&(1<<j))
                    prod=prod*divp[j+1];
            sol=sol+a/prod;
        }
        printf("%lld\n",sol);
    }
    return 0;
}