#include <bits/stdc++.h>
using namespace std;
ifstream fin ("pinex.in");
ofstream fout("pinex.out");
int nrp,prim[78500],nrd;
bool ap[100001];
long long divizor[1000];


void ciur (int n)
{
    int i,j;
    prim[++nrp]=2;
    for (i=3;i*i<=n;i+=2)
        if (ap[i]==0)
        {
        prim[++nrp]=i;
        for (j=i*i;j<=n;j+=i)
        ap[j]=1;
    }
    for (;i<=n;i+=2)
        if (ap[i]==0)
        prim[++nrp]=i;
}

void afla_div (long long x)
{
    nrd=0;
    int i,j;
    for (i=1;i<=nrp&&prim[i]*prim[i]<=x;i++)
        if (x%prim[i]==0)
    {
        while (x%prim[i]==0)
            x/=prim[i];
        divizor[++nrd]=prim[i];
    }
    if (x>1)
        divizor[++nrd]=x;
}

void pinex (long long a,long long b)
{
    int j,nrsub=(1<<nrd)-1,numar=1;
    long long ans=a;
    for (int i=1;i<=nrsub;i++)
    {
        bool ok=0;
        long long subsol=1;
        for (j=1;j<=nrd;j++)
            if ((1<<(j-1)) & numar)
                {
                    subsol*=divizor[j];
                    ok=!ok;
                }
        ++numar;
        if (ok==0)
            ans=ans+a/subsol;
        else        ans-=a/subsol;
    }
    fout<<ans<<'\n';
}

int main()
{
    int m;
    long long a,b;
    fin>>m;
    ciur (1000000);
    for (;m>0;--m)
    {
        fin>>a>>b;
        afla_div(b);
        pinex(a,b);
    }
    return 0;
}