#include <fstream>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
unsigned long long m,i,b,v[1000000],j,k,ji,p,q,s,a[1000000],aa;
bool t[1000000];
int main()
{f>>m;k=0;
for(i=2;i<=1000000;i++)
{
    if(t[i]==0)
    {k++;v[k]=i;
    for(j=i;j*i<=1000000;j++)
        t[j*i]=1;
    }
}
for(i=1;i<=m;i++)
{
    f>>aa>>b;k=0;j=1;p=1;
    while(v[j]<=sqrt(b))
    {
        if(b%v[j]==0){p=p*v[j];k++;a[k]=v[j];}
        j++;
    }
    if(b/p!=1){k++;a[k]=b/p;}
    s=0;
    for(j=1;j<(1<<k);j++)
    {p=1;q=0;
        for(ji=1;ji<=k;ji++)
        {
            if(j&(1<<(ji-1))){p=p*a[ji];q++;}
        }
    if(q%2==0)s=s-aa/p;
    else s=s+aa/p;
    }
    g<<aa-s<<'\n';
}
    return 0;
}