#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long t,a,b,n,v[101],nrc,rez,p,prim[100000],nrp;
bool ciur[NMAX];
int i,j;
int main()
{for(i=2;i<=NMAX;i++)
if(ciur[i]==0)
{
prim[++nrp]=i;
for(int j = i + i; j < NMAX; j += i)
ciur[j] = 1;
}
f>>t;
while(t--)
{f>>a>>b;
n=0;
i=1;
while (b>1 && prim[i]*prim[i]<=b)
{
if(b%prim[i]==0)
{
v[++n]=prim[i];
while(b%prim[i]==0) b=b/prim[i];
}
i++;
}
if(b>1) v[++n]=b;
rez=a;
for(i=1;i<(1LL<<n);i++)

{nrc=0;
p=1; 
for(j=0;j<n;j++)
if(i & (1LL<<j))
{
nrc++;
p=p*v[j+1];

}
if(nrc%2==1) rez=rez-a/p;
else rez=rez+a/p;
}
g<<rez<<'\n';
}
return 0;
}