#include <fstream>
#define NMAX 1000001
using namespace std;
ifstream fin("pinex.in");
ofstream fout("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;
}
fin>>t;
while(t--)
{
fin>>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;
}
fout<<rez<<'\n';
}
return 0;
}