Cod sursa(job #476063)
#include<cstdio>
#define in "pinex.in"
#define out "pinex.out"
#define MAX 1000002
long long a,b,tot,n,nrp,p[1<<20],pr[1<<20],sol[20];
void ciur()
{
bool f[MAX]={false};
for(long long i=2;i<MAX;i++)
if(!f[i])
{
p[++nrp]=i;
for(long long j=(long long)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;
}