#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

bool v[1000003], t;
long long i, j, n, pr[1000005], d[1000], calc[1000], dv, nr, nrp=80000, nrd, co;
long long a, b, k, sum;

void ler(long long t)
{
    if(t==k+1)
    {
        long long f=1;
        for(int l=1; l<=k; l++)
        {
            f=f*d[calc[l]];
        }
        sum=sum+a/f;
    }
    else
    {
        for(long long l=calc[t-1]+1; l<=nrd; l++)
        {
            calc[t]=l;
            ler(t+1);
        }
    }
}

int main()
{
    for(i=2; i<=1000000; i++)
    {
        if(v[i]==0)
        {
            co++;
            pr[co]=i;
            for(j=2; j*i<=1000000; j++)
            {
                v[i*j]=1;
            }
        }
    }
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>a>>b;
        nrd=0;
        for(nr=1; b>1&&nr<=nrp; nr++)
        {
            k=0;
            while(b%pr[nr]==0)
            {
                b/=pr[nr];
                k=1;
            }
            if(k==1){nrd++; d[nrd]=pr[nr];}
        }
        if(b>1)
        {
            nrd++;
            d[nrd]=b;
        }
        co=a;
        t=0;
        for(j=1; j<=nrd; j++)
        {
            k=j;
            sum=0;
            ler(1);
            if(t==0)
            {
                co=co-sum;
                t=1;
            }
            else
            {
                co=co+sum;
                t=0;
            }
        }
        g<<co<<'\n';
    }
    return 0;
}