#include <cstdio>
#include <cmath>
#define Bmax 1000000
using namespace std;
FILE *f1,*f2;
int prime[80000],use[1000001];
int nr_prime;
long long m,A,B,i,t,div[1000],p,n,nr,pr,j,sol,i1;

void prim()
{for (i=2;i<=Bmax;i++) use[i]=1;
nr_prime=0;
for (i=2;i<=Bmax;i++)
if (use[i])
{prime[++nr_prime]=i;
for (j=i+i;j<=Bmax;j+=i) use[j]=0;
}
}

int main()
{f1 = fopen("pinex.in","r");
f2 = fopen("pinex.out","w");
fscanf(f1,"%lld",&m);
prim();
for (i1=1;i1<=m;i1++)
{fscanf(f1,"%lld %lld",&A,&B);
p=1;n=0;
while (B>1 && prime[p]<=floor(sqrt(B)) && p<=nr_prime)
{if (B%prime[p]==0)
{div[++n]=prime[p];
while (B%prime[p]==0 && B>1) B=B/prime[p];
}
p++;
}

if (B>1) div[++n]=B;

sol=A;
for (i=1;i<(1<<n);i++)
{nr=0;pr=1;
for (j=0;j<n;j++)
if ((1<<j) & i)
{pr=pr*div[j+1];
nr++;
}
if (nr%2!=0) nr=-1;
else nr=1;
sol+=nr*A/pr;
}
fprintf(f2,"%lld\n",sol);
}
fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.